Pagini recente » Cod sursa (job #2557206) | Cod sursa (job #2067796)
#include <iostream>
#include <fstream>
#define Nmax 30005
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n, disp[4 * Nmax], lst, sums, sumd;
void query(int nod, int L, int R, int l, int r)
{
int mij = (L + R) /2;
if(l <= L && R <= r)
{
sumd += disp[nod];
return;
}
if(L > r || R < l)return;
query(2 * nod, L, mij, l, r);
query(2 * nod + 1, mij + 1, R, l, r);
}
void cupd(int nod, int L, int R, int poz)
{
int mij = (L + R) / 2;
if(L == R)
{
lst = L;
disp[nod] = 0;
return;
}
if(disp[2 * nod] >= poz)
cupd(2 * nod, L, mij, poz);
else
cupd(2 * nod + 1, mij + 1, R, poz - disp[2 * nod]);
disp[nod] = disp[2 * nod] + disp[2 * nod + 1];
}
void build(int nod, int L, int R)
{
int mij = (L + R) / 2;
if(L == R)
{
disp[nod] = 1;
return;
}
build(2 * nod, L, mij);
build(2 * nod + 1, mij + 1, R);
disp[nod] = disp[2 * nod] + disp[2 * nod + 1];
}
int main()
{
fin >> n;
lst = 1;
build(1, 1, n);
for(int i = 1; i <= n; i++)
{
sumd = 0;
if(lst != n)
query(1, 1, n, lst + 1, n);
sums = disp[1] - sumd;
if(i <= sumd)
cupd(1, 1, n, sums + i);
else
{
int caut = (i - sumd)%disp[1];
if(caut == 0)caut = disp[1];
cupd(1, 1, n, caut);
}
fout << lst << " ";
}
return 0;
}