Cod sursa(job #917665)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 11:18:51
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
const int INF = (1<<29);
int n,x[30010],i,j,a[70100],m,op,p,q;
int build(int i, int li, int ls) {
if(li > ls)
return -INF;
if(li == ls) {
a[i] = x[li];
return a[i];
}
a[i] = 
build(2*i , li, (li+ls)/2 )
+ build(2*i+1, (li+ls)/2+1, ls )
;
return a[i];
}
int chg(int i, int li, int ls, int v, int pos) {
if(pos < li || pos > ls) {
return a[i];
}
if(li == ls && li == pos) {
a[i] -= v;
return a[i];
}
return a[i] = chg(2*i, li, (li+ls)/2, v, pos) + chg(2*i+1, (li+ls)/2+1, ls, v, pos);
}
int query(int i, int li, int ls, int qi, int qs) {
if(qs < li || qi > ls)
return 0;
if(li >= qi && ls <= qs)
return a[i];
return query(2*i, li, (li+ls)/2, qi, qs) + query(2*i+1, (li+ls)/2+1, ls, qi, qs);
}
int mark(int i, int li, int ls, int q) {
a[i] --;
if(li == ls)
return li;
if(q <= a[2*i]) {
return mark(2*i, li, (li+ls)/2, q);
} else {
return mark(2*i+1, (li+ls)/2+1, ls, q-a[2*i]);
}
}
int main() {
in>>n;
for(i=1; i<=n; i++) {
x[i] = 1;
}
build(1, 1, n);
q = 2;
for(i=1; i<=n; i++) {
q = (q+i-1) % (n-i+1);
if(q == 0)
q = n-i+1;
//out<<"("<<q<<"): ";
if(q == 0)
q = n-i;
p = mark(1, 1, n, q);
out<<p<<' ';
}
return 0;
}