Pagini recente » Cod sursa (job #993526) | Cod sursa (job #739952) | Cod sursa (job #359525) | Cod sursa (job #186617) | Cod sursa (job #761434)
Cod sursa(job #761434)
#include <iostream>
#include <fstream>
using namespace std;
#define nmax 30005
ifstream f("order.in");
ofstream g("order.out");
int n, a[nmax];
struct{
int cnt;
}arb[nmax*4];
void citeste(){
f >> n;
}
void udpate(int nod, int st, int dr, int poz, int val){
if (st == dr){
if (val == -1) arb[nod].cnt = 1;
return;
}
int mij = ( st + dr) / 2;
if (poz <= mij) udpate(nod*2, st, mij, poz, val);
else udpate(nod*2+1, mij+1, dr, poz, val);
arb[nod].cnt = arb[nod*2].cnt + arb[nod*2+1].cnt;
}
int afla_pozitie(int nod, int st, int dr, int x){
if (st == dr){
return st;
}
int mij = (st + dr) / 2;
if (mij - st + 1 -arb[nod*2].cnt >= x)
return afla_pozitie(nod*2,st, mij, x);
else return afla_pozitie(nod*2+1, mij+1, dr, x-mij+st-1+arb[nod*2].cnt);
}
void rezolva(){
for(int i=1; i<=n; i++){
a[i] = i;
}
g << 2 << " ";
udpate(1,1,n,2,-1);
int prec = 2;
for(int i=2; i<=n; i++){
prec = ( prec + i -1 ) % (n-i+1);
if (prec == 0) prec = n-i+1;
int poz = afla_pozitie(1,1,n,prec);
udpate(1,1,n,poz,-1);
g << a[poz] << " ";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
}