Cod sursa(job #2428652)

Utilizator radumihaisirbuSirbu Radu-Mihai radumihaisirbu Data 5 iunie 2019 23:15:11
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("order.in");
ofstream fout ("order.out");

const int nmax = 3e4 + 5;

vector <int> arb(5*nmax);

int n, poz;

void build (int ls = 1, int ld = n, int node = 1)
{
    if (ls == ld)
    {
        arb[node] = 1;
        return;
    }

    int mid = (ls + ld) / 2;

    build(ls, mid, 2 * node);
    build(mid + 1, ld, 2 * node + 1);

    arb[node] = arb[2*node] + arb[2*node+1];
}

void query (int ls = 1, int ld = n, int node = 1, int curent = poz)
{
    if (ls == ld)
    {
        fout << ls << ' ';
        arb[node] = 0;
        return;
    }

    int mid = (ls + ld) / 2;

    if (arb[2*node] >= curent) query(ls, mid, 2 * node, curent);
    else query(mid + 1, ld, 2 * node + 1, curent - arb[2 * node]);

    arb[node] = arb[2*node] + arb[2*node+1];
}

int main()
{
    fin >> n;

    build();

    poz = 2;

    for (int i=1; i<=n; ++i)
    {
        query();

        if (i < n)
        {
            poz = (poz + i) % arb[1];
            if (poz == 0) poz = arb[1];
        }
    }
    return 0;
}