Pagini recente » Cod sursa (job #1105932) | Cod sursa (job #134727) | Cod sursa (job #1636946) | Cod sursa (job #601424) | Cod sursa (job #2903041)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("order.in");
ofstream fout("order.out");
vector <int> v(4*300005, 1);
void construct(int pos, int left, int right)
{
if(left == right)
{
v[pos] = 1;
return;
}
int mid = (left + right) / 2;
construct(pos*2, left, mid);
construct(pos*2+1, mid+1, right);
v[pos] = v[pos * 2] + v[pos * 2 + 1];
}
void update(int curr, int left, int right, int x)
{
if(left == right)
{
v[curr] = 0;
return;
}
int mid = (left + right) / 2;
if (x <= mid)
update(2 * curr, left, mid, x);
else
update(2 * curr + 1, mid + 1, right, x);
v[curr] = v[2 * curr] + v[2 * curr + 1];
}
int search(int curr, int left, int right, int pos)
{
if(left == right)
return left;
if(v[2*curr] < pos)
return search(curr * 2 + 1, (left + right) / 2 + 1, right, pos - v[curr * 2]);
return search(curr * 2, left, (left + right) / 2, pos);
}
int main()
{
int i, n, pos = 2, elem;
fin>>n;
construct(1, 1, n);
for(int i = 1; i <= n; i++)
{
pos += i;
pos --;
while(pos > v[1])
pos -= v[1];
elem = search(1, 1, n, pos);
update(1, 1, n, elem);
fout<<elem<<' ';
}
return 0;
}