Cod sursa(job #2014754)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 24 august 2017 12:54:04
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <ctime>
#define NIL -1
#define BUF_SIZE 4096
#define MAXN 300000
int x[2*MAXN-1], v[2*MAXN-1];
FILE *fin;
int pos=BUF_SIZE;
char buf[BUF_SIZE];
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
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 *fout;
    fin=fopen("congr.in", "r");
    fout=fopen("congr.out", "w");
    n=read();
    for(i=0; i<2*n-1; i++){
        x[i]=read();
        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;
}