Cod sursa(job #2108486)

Utilizator anisca22Ana Baltaretu anisca22 Data 18 ianuarie 2018 14:11:13
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
#define NMAX 30005

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

int N;
int ait[4 * NMAX];

void build(int nod, int st, int dr)
{
    if (st == dr)
    {
        ait[nod] = 1;
        return;
    }
    int mij = (st + dr) / 2;
    build(2 * nod, st, mij);
    build(2 * nod + 1, mij + 1, dr);
    ait[nod] = ait[2 * nod] + ait[2 * nod + 1];
}

int query(int nod, int L, int R, int st, int dr)
{
    if (dr < L || st > R)
        return 0;
    if (st >= L && dr <= R)
        return ait[nod];
    int mij = (st + dr) / 2;
    return query(2 * nod, L, R, st, mij) +
                query(2 * nod + 1, L, R, mij + 1, dr);
}

int update(int nod, int st, int dr, int poz)
{
    if (st == dr)
    {
        ait[nod] = 0;
        return st;
    }
    int mij = (st + dr) / 2;
    int pz;
    if (poz <= ait[2 * nod])
        pz = update(2 * nod, st, mij, poz);
    else pz = update(2 * nod + 1, mij + 1, dr, poz - ait[2 * nod]);
    ait[nod] = ait[2 * nod] + ait[2 * nod + 1];
    return pz;
}

int main()
{
    fin >> N;
    build(1, 1, N);
    int lst = 1;
    for (int i = 1; i <= N; i++)
    {
        int nr = i;
        int nr_dr = query(1, lst + 1, N, 1, N);
        int nr_st = N - i + 1 - nr_dr;
        if (i <= nr_dr)
        {
            lst = update(1, 1, N, nr_st + i);
            fout << lst << " ";
        }
        else
        {
            nr = (nr - nr_dr) % ait[1];
            if (nr == 0)
                nr = ait[1];
            lst = update(1, 1, N, nr);
            fout << lst << " ";
        }
    }
    return 0;
}