Pagini recente » Cod sursa (job #2627954) | Cod sursa (job #2302359) | Cod sursa (job #2194684) | Cod sursa (job #1391984) | Cod sursa (job #3245251)
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int NMAX = 30005;
int st[4 * NMAX], n;
int nr = 1; // st[x] => suma val de 1 pe interval (nr copii existenti)
void Build(int x, int l, int r)
{
if (l == r)
{
st[x] = 1;
return;
}
int m = (l + r) / 2;
Build(2 * x, l, m);
Build(2 * x + 1, m + 1, r);
st[x] = st[2 * x] + st[2 * x + 1];
}
void Update(int x, int l, int r, int nr)
{
if (l == r)
{
fout << l << " "; // gasim copilul
st[x] = 0; // il stergem
return;
}
int m = (l + r) / 2;
if (nr <= st[2 * x])
Update(2 * x, l, m, nr);
else
Update(2 * x + 1, m + 1, r, nr - st[2 * x]);
st[x] = st[2 * x] + st[2 * x + 1];
}
int main()
{
fin >> n;
Build(1, 1, n);
for (int i = 1 ; i <= n ; i++)
{
// la cati mai erau adaug cati trebuie sa mai fie la pasul curent
nr += i; // nr copii care trebuie sa mai existe incepand de la poz 1 (pe ultimul il sterg)
if (nr <= st[1]) // daca mai sunt suficienti copii pe cerc (st[1] = nr total existenti pe cerc)
{
Update(1, 1, n, nr); // sterg 1
nr--;
}
else
{
nr = (nr - 1) % st[1] + 1; // cati trebuie sa mai existe incepand de la poz 1
Update(1, 1, n, nr);
nr--;
}
}
return 0;
}