Pagini recente » Istoria paginii runda/nxdtjsyksrjs | Cod sursa (job #3264205) | Clasamentul arhivei Infoarena Monthly | Clasamentul arhivei Infoarena Monthly | Cod sursa (job #3261060)
#include <stdio.h>
#define MAXN 30001
struct fenwick{
private:
int aib[MAXN];
int n;
void update(int idx, int val){
while(idx<=n){
aib[idx] += val;
idx+=(idx&-idx);
}
}
public:
void init(int n){
this->n = n;
}
void add(int idx){
update(idx, 1);
}
void del(int idx){
update(idx, -1);
}
int query(int idx){
int sum = 0;
while(idx>0){
sum+=aib[idx];
idx -= (idx&-idx);
}
return sum;
}
};
int n;
fenwick aib;
int main(){
FILE *fin, *fout;
fin = fopen("order.in", "r");
fscanf(fin, "%d", &n);
fclose(fin);
aib.init(n);
for(int i=1; i<=n; i++){
aib.add(i);
}
fout = fopen("order.out", "w");
int pos = 2;
int remain = n;
int i = 0;
while(remain>0){
pos = (pos+i)%remain;
if(!pos) pos = remain;
remain--;
int s = 0;
int d = n;
while(d-s>1){
int m = (s+d)/2;
if(aib.query(m)<pos) s = m;
else d = m;
}
aib.del(d);
fprintf(fout, "%d ", d);
i++;
}
fclose(fout);
return 0;
}