Cod sursa(job #3296652)

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

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

void update_recursiv(int nod, int stanga, int dreapta, int poz, int val)
{
    if (stanga == dreapta)
    {
        aint[nod] = val;
        return;
    }
    int mij = (stanga + dreapta) / 2;
    if (poz <= mij)
        update_recursiv(2 * nod, stanga, mij, poz, val);
    else
        update_recursiv(2 * nod + 1, mij + 1, dreapta, 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 stanga, int dreapta, int query_x, int query_y)
{
    if (query_x > query_y)
        return 0;

    if (stanga == query_x && dreapta == query_y)
        return aint[nod];

    int mij = (stanga + dreapta) / 2;
    if (query_y <= mij)
        return query_recursiv(2 * nod, stanga, mij, query_x, query_y);
    if (query_x > mij)
        return query_recursiv(2 * nod + 1, mij + 1, dreapta, query_x, query_y);
    return query_recursiv(2 * nod, stanga, mij, query_x, mij) + query_recursiv(2 * nod + 1, mij + 1, dreapta, mij + 1, query_y);
}

int query(int query_x, int query_y)
{
    return query_recursiv(1, 1, n, query_x, query_y);
}

int cautbinar(int p, int stanga)
{
    int st = stanga, dr = n, sol = -1;

    while (st <= dr)
    {
        int m = (st + dr) / 2;
        int locuri_libere = query(stanga, m);

        if (locuri_libere >= p)
        {
            sol = m;
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }

    if (sol == -1)
    {
        st = 1, dr = stanga - 1;
        while (st <= dr)
        {
            int m = (st + dr) / 2;
            int locuri_libere = query(st, m);

            if (locuri_libere >= p - query(stanga, n))
            {
                sol = m;
                dr = m - 1;
            }
            else
            {
                st = m + 1;
            }
        }
    }

    return sol;
}

int formula(int i, int poz)
{
    return (poz + i - 2) % n + 1;
}

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 = 2;
    for (int i = 1; i <= n; i++)
    {
        int pf = formula(i, poz);
        int total = query(1, n);
        int target = (i % total == 0) ? total : i % total;

        int eliminat = cautbinar(target, pf);
        raspuns[i] = eliminat;
        update(eliminat, 0);
        poz = eliminat % n + 1;
    }

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

    return 0;
}