Pagini recente » Cod sursa (job #2859581) | Cod sursa (job #2632143) | Cod sursa (job #1315161) | Cod sursa (job #1002234) | Cod sursa (job #3137657)
#include <bits/stdc++.h>
using namespace std;
int n;
class Fenwick
{
vector <int> a;
int _n;
public :
Fenwick (int n)
{
a.resize(n + 1);
_n = n;
}
int lsb(int i)
{
return (i & (-i));
}
void update(int poz, int val)
{
for(int i = poz; i <= _n; i += lsb(i))
a[i] += val;
}
int query(int poz)
{
int ans = 0;
for(int i = poz; i >= 1; i -= lsb(i))
ans += a[i];
return ans;
}
int binarySearch(int x)
{
int r, pas, cursum = 0;
r = 0;
pas = 1 << 17;
while (pas)
{
if (r + pas <= n && cursum + a[r + pas] < x)
{
cursum += a[r + pas];
r += pas;
}
pas >>= 1;
}
return r + 1;
}
};
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
cin >> n;
Fenwick aib(n);
for(int i = 1; i <= n; i ++)
aib.update(i, 1);
// aib.print();
int poz = 1;
for(int jump = 1; jump <= n; jump ++)
{
int before, total, currJump;
before = aib.query(poz);
currJump = before + jump;
total = aib.query(n);
if(currJump % total)
currJump %= total;
else
currJump = total;
poz = aib.binarySearch(currJump);
cout << poz << " ";
aib.update(poz, -1);
}
return 0;
}