Mai intai trebuie sa te autentifici.
Cod sursa(job #1775170)
Utilizator | Data | 9 octombrie 2016 22:57:20 | |
---|---|---|---|
Problema | Order | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.99 kb |
#include <stdio.h>
#define lim 300005
int aib[lim],n;
int zeros(int x){return (x&(x-1))^x;}
void update(int poz,int val){
while(poz<=n){
aib[poz]+=val;
poz+=zeros(poz);
}
}
int query(int poz){
int s=0;
while(poz!=0){
s+=aib[poz];
poz-=zeros(poz);
}
return s;
}
int cautbin(int val){
int i=0,pas=1<<18;
while(pas!=0){
if(i+pas<=n&&query(i+pas)<=val)
i+=pas;
pas/=2;
}
while(query(i)==val)
i--;
return i+1;
}
int main(){
FILE *fin,*fout;
fin=fopen("order.in","r");
fout=fopen("order.out","w");
int i,val,elim;
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++)
update(i,1);
val=1;
for(i=1;i<=n;i++){
val=(val+i)%(n-i+1);
if(val==0)
val=n-i+1;
elim=cautbin(val);
fprintf(fout,"%d ",elim);
update(elim,-1);
val--;
}
fclose(fin);
fclose(fout);
return 0;
}