Pagini recente » Cod sursa (job #1242443) | Cod sursa (job #1331792) | Cod sursa (job #1090230) | Cod sursa (job #811518) | Cod sursa (job #2902992)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("order.in");
ofstream fout("order.out");
int n;
vector <int> v(4*300005, 1);
void construct(int pos, int left, int right)
{
if(left == right)
{
v[pos] = 1;
return;
}
v[n] = right - left + 1;
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 pos, int x)
{
if(pos < left || pos > right) return;
if(left == right)
{
v[curr] = x;
return;
}
update(curr * 2, left, (left + right) / 2, pos, x);
update(curr * 2 + 1, (left + right) / 2 + 1, right, pos, x);
v[curr] = v[curr * 2] + v[curr * 2 + 1];
}
int solve(int curr, int left, int right, int pos)
{
if(left == right)
{
fout << left << ' ';
return left;
}
if(v[2*curr] < pos)
return solve(curr * 2 + 1, (left + right) / 2 + 1, right, pos - v[curr * 2]);
return solve(curr * 2, left, (left + right) / 2, pos);
}
int main()
{
fin>>n;
int left = n, pos = 2;
construct(1, 1, n);
for(int i = 1; i <= n; i++)
{
pos = (i+pos-1)%left;
if(pos==0) pos==left;
left--;
int x = solve(1, 1, n, pos);
update(1, 1, n, x, 0);
}
return 0;
}