Pagini recente » Cod sursa (job #1341186) | Cod sursa (job #2139412) | Cod sursa (job #866065) | Cod sursa (job #2315007) | Cod sursa (job #2605732)
#include <bits/stdc++.h>
#define MAX 30005
#define last_bit(i)(i & (-i))
using namespace std;
int n;
int aib[MAX];
bool scos[MAX];
int query(int x)
{
int sol = 0;
while(x)
{
sol += aib[x];
x -= last_bit(x);
}
return sol;
}
void update(int x)
{
while(x <= n)
{
aib[x]--;
x += last_bit(x);
}
}
int main()
{
ifstream fin("order.in");
ofstream fout("order.out");
//ios::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin >> n;
for(int i = 1; i <= n; i++)
aib[i] = i - (i - last_bit(i));
int p = 1;
for(; (p << 1) <= n; p <<= 1);
int remained = n, currPos = 1;
for(int i = 1; i <= n; i++)
{
int copyI = i;
i %= remained;
if(!i)i = remained;
int gasit = currPos;
int dif = query(currPos);
for(int j = p; j; j >>= 1)
if(gasit + j <= n && query(gasit + j) - dif <= i)
gasit += j;
while(scos[gasit])
{
gasit--;
if(!gasit)gasit = n;
}
if(query(gasit) - dif == i)
{
fout << gasit << " ";
scos[gasit] = 1;
update(gasit);
currPos = gasit;
}
else
{
int solCurr = query(gasit) - dif;
int gasit = 0;
for(int j = p; j; j >>= 1)
if(gasit + j <= n && query(gasit + j) + solCurr <= i)
gasit += j;
while(scos[gasit])
{
gasit--;
if(!gasit)gasit = n;
}
fout << gasit << " ";
scos[gasit] = 1;
update(gasit);
currPos = gasit;
}
remained--;
i = copyI;
}
fin.close();
fout.close();
return 0;
}