Cod sursa(job #3363565)

Utilizator Alexutu008Ionita Alexandru-Dumitru Alexutu008 Data 19 august 2026 13:33:00
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

const int max_size = 3e4 + 1, max_seg = 12e4 + 1;
int n, aint[max_seg], offset = 1, place, tg, tura;

void init(int l, int r, int nod)
{
    if (l == r)
    {
        if (l <= n)
            aint[nod] = 1;
        return;
    }
    int m = l + r >> 1;
    init(l, m, nod << 1);
    init(m + 1, r, (nod << 1) + 1);
    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

int query(int l, int r, int sum, int nod)
{
    if (l == r)
    {
        offset = l;
        return nod;
    }
    int m = l + r >> 1;
    if (aint[nod * 2] >= sum)
        return query(l, m, sum, nod << 1);
    else
        return query(m + 1, r, sum - aint[nod * 2], nod * 2 + 1);
}

int sum_ij(int l, int r, int st, int dr, int nod)
{
    if (st <= l && r <= dr)
        return aint[nod];
    int m = l + r >> 1, p1 = 0, p2 = 0;
    if (st <= m)
        p1 = sum_ij(l, m, st, dr, nod << 1);
    if (m + 1 <= dr)
        p2 = sum_ij(m + 1, r, st, dr, nod * 2 + 1);
    return p1 + p2;
}

void update(int nod)
{
    while (nod >= 1)
    {
        aint[nod]--;
        nod >>= 1;
    }
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    init(1, n, 1);
    // cout<<query(1, n, 2, 1)<<' '<<offset;
    for (int i = 1; i <= n; ++i)
    {
        int nxt = sum_ij(1, n, offset + 1, n, 1);
        if (nxt >= i)
            {tg = offset + i - tura;++tura;}
        else
        {
            tg = i - nxt;
            tura=1;
            while(tg>aint[1]) tg-=aint[1];
        }
        place = query(1, n, tg, 1);
        update(place);
        cout << offset << ' ';
        // offset = i+offset;
    }

    return 0;
}