Pagini recente » Cod sursa (job #3252901) | Cod sursa (job #620590) | Cod sursa (job #2948001) | Cod sursa (job #2814904) | Cod sursa (job #3193915)
//https://www.infoarena.ro/problema/order
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
#define MAXN 100000
int n;
vector <int> bit(MAXN + 1, 0);
void update(int i, int val)
{
while (i <= n)
{
bit[i] += val;
i += (i & -i);
}
}
int prefixSum(int i)
{
int sum;
sum = 0;
while (i > 0)
{
sum += bit[i];
i -= (i & -i);
}
return sum;
}
int main()
{
cin >> n;
int i;
for (i = 1; i <= n; i++)
update(i, 1);
int poz, dr, st, mij;
poz = 2;
for (i = 1; i <= n; i++)
{
poz = (poz + n - 1) % (n - i + 1) + 1;
st = 1;
dr = n;
while (st < dr)
{
mij = (st + dr) / 2;
if (prefixSum(mij) >= poz)
dr = mij;
else
st = mij + 1;
}
cout << dr << " ";
update(dr, -1);
}
return 0;
}