Cod sursa(job #3137656)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 14 iunie 2023 10:02:29
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#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);
        currJump %= total;
        if(!currJump)
            currJump = 1;
//        cout << currJump << " " << before << " " << total << " ";
        poz = aib.binarySearch(currJump);
        cout << poz << " ";
        aib.update(poz, -1);
    }
    return 0;
}