Cod sursa(job #1575009)
Utilizator | 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;
}