Cod sursa(job #2741036)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 15 aprilie 2021 12:28:15
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define nozerous(x) (x & -x)
#define MOD 1000000007
using namespace std;

const int INF = (1 << 30), NMAX(30005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

int ARB[4 * NMAX + 5], AIB[NMAX], n, wh, care[4 * NMAX + 5], ch;

void Add(int poz, int val)
{
    for(; poz <= n; poz += nozerous(poz))
        AIB[poz] += val;
}

int Query(int poz)
{
    int rez = 0;
    for(; poz >= 1; poz -= nozerous(poz))
        rez += AIB[poz];
    return rez;
}

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

void query(int nod, int st, int dr, int cat)
{
    if(st == dr)
    {
        wh = care[nod];
        return;
    }
    int mij = (st + dr) / 2;
    if(ARB[2 * nod] < cat)
        query(2 * nod + 1, mij + 1, dr, cat - ARB[2 * nod]);
    else query(2 * nod, st, mij, cat);
}

int main()
{
    BUNA("order");
    cin >> n;

    for(int i = 1; i <= n; ++i)
    {
        ch = i;
        update(1, 1, n, i, 1);
        Add(i, 1);
    }

    int curPoz = 2;
    int nrPas = 2;
    while(ARB[1] > 0)
    {
        cout << curPoz << ' ';
        Add(curPoz, -1);
        update(1, 1, n, curPoz, 0);
        if(ARB[1] == 0)
            break;
        int rem = Query(n) - Query(curPoz);
        if(rem >= nrPas)
            query(1, 1, n, Query(curPoz) + nrPas);
        else
        {
            int need = nrPas - rem;
            need %= ARB[1];
            if(need == 0)
                need = ARB[1];
            query(1, 1, n, need);
        }
        curPoz = wh;
        ++nrPas;
    }
    PA();
}