[ZJ] a814. 2013高雄市能力競賽高中組 5. 卡片遊戲

#include<stdio.h>
#include<string.h>
#define lowbit(x) (x&-x)
int s[1000005],v[1000005]={0},C[1000005]={0},m;
int cnt(int k){
    int i,add=0;
    for(i=k;i>0;i-=lowbit(i))
        add+=C[i];
    return add;
}
void add(int k,int v){
    int i;
    for(i=k;i<=m;i+=lowbit(i))
        C[i]+=v;
}
int main(){
    int t,n,i,j,p,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(C,0,4*m+10);
        memset(v,0,4*m+10);
        for(i=0;i<n;i++)
            scanf("%d",&s[i]);
        for(i=0;i<n;i++){
            p=s[i];
            add(s[i],1);
            if(v[p] || i==n-1){
                v[p]++;
                break;
            }
            v[p]++;
        }

        for(j=i;j>=0;j--){//printf("%d...",cnt(19));
            add(s[j],-1);
            v[s[j]]--;
            if(m-s[j]>cnt(m)-cnt(s[j]) || j==0) break;
        }
        for(i=0;i<j;i++) printf("%d ",s[i]);
        k=n-j-1;
        for(i=s[j]+1;i<=m;i++){
            if(v[i]==0){
                v[i]=1;

                printf("%d ",i);
                break;
            }
        }
        for(i=1;i<=m && k;i++){
            if(v[i]==0){
                k--;
                printf("%d ",i);
            }
        }
        puts("");
        go:;
    }
}