Nu aveti permisiuni pentru a descarca fisierul logo_runda2.gif
Cod sursa(job #1425381)
Utilizator | Data | 27 aprilie 2015 13:16:50 | |
---|---|---|---|
Problema | Order | Scor | 0 |
Compilator | c | Status | done |
Runda | Arhiva de probleme | Marime | 0.94 kb |
#include<stdio.h>
#define N 30000
int v[N+1],n;
void update(int poz,int val){
while(poz<=n){
v[poz]+=val;
poz+=(poz&-poz);
}
}
int sum(int poz){
int s=0;
while(poz){
s+=v[poz];
poz&=poz-1;
}
return s;
}
int cauta(int poz){
int st=1,dr=n;
while(st<=dr){
int mij=(st+dr)/2;
if(sum(mij)==poz)
return mij;
if(sum(mij)<poz)
st=mij+1;
else
dr=mij-1;
}
return -1;
}
int main(){
FILE *fin,*fout;
fin=fopen("order.in","r");
fout=fopen("order.out","w");
fscanf(fin,"%d",&n);
int i;
for(i=1; i<=n; i++)
update(i,1);
int pos=1;
for(i=1; i<=n; i++){
pos=(pos+i)%(n-i+1);
if(pos==0)
pos=n-i+1;
int poz=cauta(pos);
fprintf(fout,"%d ",poz);
update(poz,-1);
pos=sum(poz);
}
return 0;
}