Cod sursa(job #2771511)

Utilizator mihai_popaPopa Mihai-Razvan mihai_popa Data 27 august 2021 18:02:10
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 3 * 1e5 + 4;
int aint[4 * NMAX], n, pos, copilAfara;

int newPos(int pos, int t)
{
    ///daca copilul de la pasul t - 1 se afla la pozitia pos (si acel copil a iesit din joc), urmatorul se va afla la pozitia pos + t - 1;

    pos += t - 1;
    pos = pos % aint[1];
    if(pos == 0) pos = aint[1];

    return pos;
}

void build(int nod, int L, int R)
{
    if(L == R){
        aint[nod] = 1;
        return;
    }
    int mid = (L + R) >> 1;

    build(2 * nod, L, mid);
    build(2 * nod + 1, mid + 1, R);

    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void update(int nod, int L, int R, int val) ///arbore de intervale cu sume
{
    if(L == R){
        aint[nod] = 0;
        return;
    }

    int mid = (L + R) >> 1;

    if(val <= mid) update(2 * nod, L, mid, val);
    else update(2 * nod + 1, mid + 1, R, val);

    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

int query(int nod, int L, int R, int val) /// caut capatul din dreapta D cu proprietatea ca D se afla in [L...R] si [L...D] contine val elemente;
{
    if(L == R)
        return L;

    int mid = (L + R) >> 1;
    if(aint[2 * nod] >= val) ///fiul din stanga (interval [L...mid]) >= val    --> D se afla in intervalul [L...mid];
        return query(2 * nod, L, mid, val);
    else /// [L...mid] = x, x <= val   -> D se afla in intervalul [mid + 1...R] si trebuie cautata valoarea pentru care [mid + 1...D] = val - x;
        return query(2 * nod + 1, mid + 1, R, val - aint[2 * nod]);

}

int main()
{
    fin >> n;
    pos = 2;

    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        pos = newPos(pos, i);
        copilAfara = query(1, 1, n, pos);
        update(1, 1, n, copilAfara);

        fout << copilAfara << " ";
    }
    return 0;
}