Cod sursa(job #3296654)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 15 mai 2025 10:14:45
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
using namespace std;

const int NMAX = 1000001;
int raspuns[NMAX], aint[4 * NMAX], n;

void update_recursiv(int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        aint[nod] = val;
        return;
    }
    int mij = (st + dr) / 2;
    if (poz <= mij)
        update_recursiv(2 * nod, st, mij, poz, val);
    else
        update_recursiv(2 * nod + 1, mij + 1, dr, poz, val);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void update(int poz, int val)
{
    update_recursiv(1, 1, n, poz, val);
}

int query_recursiv(int nod, int st, int dr, int x, int y)
{
    if (x > y)
        return 0;
    if (st == x && dr == y)
        return aint[nod];
    int mij = (st + dr) / 2;
    if (y <= mij)
        return query_recursiv(2 * nod, st, mij, x, y);
    if (x > mij)
        return query_recursiv(2 * nod + 1, mij + 1, dr, x, y);
    return query_recursiv(2 * nod, st, mij, x, mij) + query_recursiv(2 * nod + 1, mij + 1, dr, mij + 1, y);
}
int query(int x, int y)
{
    return query_recursiv(1, 1, n, x, y);
}

int caut_binar(int k, int start)
{
    int total_dreapta = query(start, n);
    if (total_dreapta >= k)
    {
        int st = start, dr = n, sol = -1;
        while (st <= dr)
        {
            int mij = (st + dr) / 2;
            if (query(start, mij) >= k)
            {
                sol = mij;
                dr = mij - 1;
            }
            else
                st = mij + 1;
        }
        return sol;
    }
    else
    {
        k -= total_dreapta;
        int st = 1, dr = n, sol = -1;
        while (st <= dr)
        {
            int mij = (st + dr) / 2;
            if (query(1, mij) >= k)
            {
                sol = mij;
                dr = mij - 1;
            }
            else
                st = mij + 1;
        }
        return sol;
    }
}

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

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        update(i, 1);

    int poz = 1;
    for (int i = 1; i <= n; i++)
    {
        int ramasi = query(1, n);
        int pas = i % ramasi;
        if (pas == 0)
            pas = ramasi;

        int eliminat = caut_binar(pas, poz);
        raspuns[i] = eliminat;
        update(eliminat, 0);

        if (i < n)
        {
            poz = eliminat % n + 1;
            while (query(poz, poz) == 0)
            {
                poz++;
                if (poz > n)
                    poz = 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", raspuns[i]);

    return 0;
}