Cod sursa(job #2548101)

Utilizator pregoliStana Andrei pregoli Data 16 februarie 2020 11:05:43
Problema Order Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
///************************

int n;
const int NMAX = 3e4+5;
int aint[NMAX * 4];

void build(int nod, int l, int r)
{
    if (l == r)
    {
        aint[nod] = 1;
        return;
    }

    int mid = (l + r) / 2;
    build(nod * 2, l, mid);
    build(nod * 2 + 1, mid + 1, r);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void update(int nod, int l, int r, int pos, int x)
{
    if (l == r)
    {
        aint[nod] += x;
        return;
    }

    int mid = (l + r) / 2;
    if (pos <= mid)
        update(nod * 2, l, mid, pos, x);
    else
        update(nod * 2 + 1, mid + 1, r, pos, x);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

int query(int nod, int l, int r, int ql, int qr)
{
    if (qr < ql)
        return 0;
    if (l == ql && r == qr)
    {
        return aint[nod];
    }

    int mid = (l + r) / 2;
    if (qr <= mid)
        return query(nod * 2, l, mid, ql, qr);
    else if (mid < ql)
        return query(nod * 2 + 1, mid + 1, r, ql, qr);
    else
        return query(nod * 2, l, mid, ql, mid) + query(nod * 2 + 1, mid + 1, r, mid + 1, qr);
}

int bin_src(int x, int l, int r)
{
    int ans;
    int auxleft = l;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        int val = query(1, 1, n, auxleft, mid);
        if (val == x)
        {
            ans = mid;
            r = mid - 1;
        }
        else if (val > x)
            r = mid - 1;
        else
            l = mid + 1;
    }

    return ans;
}

int main()
{
    fin >> n;
    build(1, 1, n);
    int pos = 1;
    for (int step = 1; step <= n; step++)
    {
        int q = query(1, 1, n, pos + 1, n);
        if (q >= step)
        {
            int x = bin_src(step, pos + 1, n);
            fout << x << ' ';
            pos = x;
            update(1, 1, n, pos, -1);
        }
        else
        {
            int rem = step - q;//remaining kids
            int mod = rem % (n - step + 1);

            if (!mod)
                mod = n - step + 1;

            int x = bin_src(mod, 1, n);
            fout << x << ' ';
            pos = x;
            update(1, 1, n, pos, -1);
        }
    }

    fout.close();
    return 0;
}