Cod sursa(job #2461593)

Utilizator IonAdrianIon Adrian IonAdrian Data 25 septembrie 2019 21:07:15
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

struct Bit
{
    vector <ll> aib;
    int n;
    void init (int x)
    {
        n = x;
        aib.resize (n + 1);
    }
    int lsb (int x)
    {
        return x & -x;
    }
    void add (ll val, int pos)
    {
        while (pos <= n)
        {
            aib[pos] += val;
            pos += lsb (pos);
        }
    }
    ll query (int pos)
    {
        ll ans = 0;
        while (pos)
        {
            ans += aib[pos];
            pos -= lsb (pos);
        }
        return ans;
    }
};

int main() {
    freopen ("order.in", "r", stdin);
    freopen ("order.out", "w", stdout);

    Bit aib;
    cin >> n;
    aib.init (n * 2);
    for (int i = 1; i <= 2 * n; i++)
        aib.add (1, i);

    int cur = 0;
    int k = 1;
    int left = n;
    for (int steps = 0; steps < n; steps++)
    {
        if (cur)
        {
            aib.add (-1, cur);
            aib.add (-1, cur + n);
        }
        else cur++;

        int l, r, ans = 0;
        l = cur;
        r = 2 * n;
        int kk = (k - 1) % left + 1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (aib.query (mid) - aib.query (cur) >= kk)
            {
                ans = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        if (ans > n)
            ans -= n;
        cur = ans;
        cout << cur << " ";
        k++;
        left--;
    }
    return 0;
}