Cod sursa(job #3274025)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 4 februarie 2025 19:38:41
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
int n, cnt, pos = 2, val;
vector<int> aib;
void update(int node, int val)
{
    for(; node <= n; node += node&(-node))
        aib[node] += val;
}

int bs(int val)
{
    int ans = 0, csum = 0;
    for(int step = (1 << 15); step > 0; step /= 2)
        if(ans + step <= n && csum + aib[ans + step] < val)
        {
            ans += step;
            csum += aib[ans];
        }
    return ans + 1;
}

int main()
{
    cin >> n;
    cnt = n;
    aib.resize(n+1);
    for(int i=1; i<=n; i++)
        update(i, 1);
    for(int i=1; i<=n; i++)
    {
        pos = (pos + i - 1) % cnt;

        if(pos == 0)
            pos = cnt;
        int ans = bs(pos);
        update(ans , -1);
        cout << ans << " ";
        cnt --;
    }
    return 0;
}