Pagini recente » Cod sursa (job #2320894) | Cod sursa (job #981893) | Cod sursa (job #2410237) | Cod sursa (job #975250) | Cod sursa (job #2771511)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("order.in"); ofstream fout("order.out");
const int NMAX = 3 * 1e5 + 4;
int aint[4 * NMAX], n, pos, copilAfara;
int newPos(int pos, int t)
{
///daca copilul de la pasul t - 1 se afla la pozitia pos (si acel copil a iesit din joc), urmatorul se va afla la pozitia pos + t - 1;
pos += t - 1;
pos = pos % aint[1];
if(pos == 0) pos = aint[1];
return pos;
}
void build(int nod, int L, int R)
{
if(L == R){
aint[nod] = 1;
return;
}
int mid = (L + R) >> 1;
build(2 * nod, L, mid);
build(2 * nod + 1, mid + 1, R);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void update(int nod, int L, int R, int val) ///arbore de intervale cu sume
{
if(L == R){
aint[nod] = 0;
return;
}
int mid = (L + R) >> 1;
if(val <= mid) update(2 * nod, L, mid, val);
else update(2 * nod + 1, mid + 1, R, val);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
int query(int nod, int L, int R, int val) /// caut capatul din dreapta D cu proprietatea ca D se afla in [L...R] si [L...D] contine val elemente;
{
if(L == R)
return L;
int mid = (L + R) >> 1;
if(aint[2 * nod] >= val) ///fiul din stanga (interval [L...mid]) >= val --> D se afla in intervalul [L...mid];
return query(2 * nod, L, mid, val);
else /// [L...mid] = x, x <= val -> D se afla in intervalul [mid + 1...R] si trebuie cautata valoarea pentru care [mid + 1...D] = val - x;
return query(2 * nod + 1, mid + 1, R, val - aint[2 * nod]);
}
int main()
{
fin >> n;
pos = 2;
build(1, 1, n);
for(int i = 1; i <= n; i++){
pos = newPos(pos, i);
copilAfara = query(1, 1, n, pos);
update(1, 1, n, copilAfara);
fout << copilAfara << " ";
}
return 0;
}