Cod sursa(job #2067796)

Utilizator leraValeria lera Data 16 noiembrie 2017 20:35:39
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#define Nmax 30005
using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");
int n, disp[4 * Nmax], lst, sums, sumd;
void query(int nod, int L, int R, int l, int r)
{
    int mij = (L + R) /2;
    if(l <= L && R <= r)
    {
        sumd += disp[nod];
        return;
    }
    if(L > r || R < l)return;
    query(2 * nod, L, mij, l, r);
    query(2 * nod + 1, mij + 1, R, l, r);
}
void cupd(int nod, int L, int R, int poz)
{
    int mij = (L + R) / 2;
    if(L == R)
    {
        lst = L;
        disp[nod] = 0;
        return;
    }
    if(disp[2 * nod] >= poz)
        cupd(2 * nod, L, mij, poz);
    else
        cupd(2 * nod + 1, mij + 1, R, poz - disp[2 * nod]);
    disp[nod] = disp[2 * nod] + disp[2 * nod + 1];
}
void build(int nod, int L, int R)
{
    int mij = (L + R) / 2;
    if(L == R)
    {
        disp[nod] = 1;
        return;
    }
    build(2 * nod, L, mij);
    build(2 * nod + 1, mij + 1, R);
    disp[nod] = disp[2 * nod] + disp[2 * nod + 1];
}
int main()
{
    fin >> n;
    lst = 1;
    build(1, 1, n);
    for(int i = 1; i <= n; i++)
    {
        sumd = 0;
        if(lst != n)
        query(1, 1, n, lst + 1, n);

        sums = disp[1] - sumd;
        if(i <= sumd)
            cupd(1, 1, n, sums + i);
        else
        {
            int caut = (i - sumd)%disp[1];
            if(caut == 0)caut = disp[1];
            cupd(1, 1, n, caut);
        }
        fout << lst << " ";
    }
    return 0;
}