Pagini recente » Cod sursa (job #3185644) | Cod sursa (job #2382437) | Cod sursa (job #1803534) | Cod sursa (job #659404) | Cod sursa (job #761416)
Cod sursa(job #761416)
#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;
}
a[2] = -1;
udpate(1,1,n,2,-1);
int poz = 2;
g << 2 << " ";
int s = 2;
for(int i=2; i<=n-1; i++){
int x = poz % (n-i+1);
int nou = poz + x - 1;
if (nou > (n-i+1) ) nou = nou - (n-i+1);
//cout << nou << "\n";
int cpy = nou;
nou = afla_pozitie(1, 1, n, nou);
g << a[nou] << " ";
s+=a[nou];
a[nou] = -1;
udpate(1,1,n,nou,-1);
poz = cpy;
}
g << (((n*(n+1))/2 ) - s) << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
}