Cod sursa(job #1575009)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 21 ianuarie 2016 00:26:45
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <cstdio>
#include <cstdlib>
#define NIL -1
#define MAXN 300000
int x[2*MAXN-1], v[2*MAXN-1], fr[MAXN], ok[MAXN];
inline void swap(int a, int b){
    int aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
int main(){
    int n, ans, i, p, a, b, cat, r, sum;
    FILE *fin, *fout;
    fin=fopen("congr.in", "r");
    fout=fopen("congr.out", "w");
    fscanf(fin, "%d", &n);
    ans=NIL;
    for(i=0; i<2*n-1; i++){
        fscanf(fin, "%d", &x[i]);
        x[i]%=n;
        fr[x[i]]++;
        v[i]=i;
        if(x[i]==0){
            ans=i;
        }
    }
    if(ans!=NIL){
        fprintf(fout, "%d\n", ans+1);
    }else{
        for(i=1; i<n; i++){
            if((fr[i]>0)&&(fr[n-i]>0)){
                ans=i;
            }
        }
        if(ans!=NIL){
            a=ans;
            b=n-ans;
            for(i=0; i<2*n-1; i++){
                if(x[i]==a){
                    fprintf(fout, "%d ", i+1);
                    a=NIL;
                }
                if(x[i]==b){
                    fprintf(fout , "%d ", i+1);
                    b=NIL;
                }
            }
        }else{
            for(i=1; i<n; i++){
                if(fr[i]>=n){
                    ans=i;
                }
            }
            if(ans!=NIL){
                cat=n;
                for(i=0; i<n; i++){
                    if((cat>0)&&(x[i]==ans)){
                        fprintf(fout, "%d ", i+1);
                    }
                }
            }else{
                r=0;
                while(ans!=NIL){
                    p=rand()%(2*n-1);
                    if(p<r){
                        fr[x[v[p]]]++;
                        sum-=x[v[p]];
                        if(sum<0){
                            sum+=n;
                        }
                        r--;
                        swap(p, r);
                    }else{
                        fr[x[v[p]]]--;
                        sum+=x[v[p]];
                        if(sum>=n){
                            sum-=n;
                        }
                        swap(p, r);
                        r++;
                    }
                    if(sum==0){
                        ans=1;
                        for(i=0; i<r; i++){
                            fprintf(fout, "%d ", v[i]+1);
                        }
                    }else if(fr[n-sum]>0){
                        ans=1;
                        for(i=0; i<r; i++){
                            fprintf(fout, "%d ", v[i]+1);
                            ok[v[i]]=1;
                        }
                        for(i=0; i<2*n-1; i++){
                            if((ans==1)&&(ok[i]==0)&&(x[i]==n-sum)){
                                fprintf(fout, "%d ", i+1);
                                ans=0;
                            }
                        }
                    }
                }
            }
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}