Cod sursa(job #1575020)

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