Cod sursa(job #1597663)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 12 februarie 2016 11:07:23
Problema Order Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream is("order.in");
ofstream os("order.out");

using VI = vector<int>;

int n, beg, elim, poz;
VI a, ok;

void Build(int nod, int st, int dr);
void Update(int nod, int st, int dr);
int Sum(int nod, int st, int dr);

int main()
{
    is >> n;
    a = VI(4 * n + 1);
    ok = VI(n + 1);
    Build(1, 1, n);
    beg = 1;
    for ( int i = 1; i <= n; ++i )
    {
        elim = i;
        while ( elim )
        {
            ++beg;
            if ( beg > n )
                beg = 1;
            if ( !ok[beg] )
                --elim;
        }
        poz = beg;
        Update(1, 1, n);
    }
    is.close();
    os.close();
    return 0;
}

int Sum(int nod, int st, int dr)
{
    if ( st == dr )
        return a[nod];
    int md = ( st + dr ) / 2;
    if ( poz <= md )
        return Sum(2 * nod, st, md);
    else
        return a[2 * nod] + Sum(2 * nod + 1, md + 1, dr);
}

void Update(int nod, int st, int dr)
{
    if ( st == dr )
    {
        a[nod] = 0;
        os << st << " ";
        ok[st] = 1;
        beg = st;
        return;
    }
    int md = ( st + dr ) / 2;
    if ( poz <= md )
        Update(2 * nod, st, md);
    else
        Update(2 * nod + 1, md + 1, dr);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}

void Build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        a[nod] = 1;
        return;
    }
    int md = ( st + dr ) / 2;
    Build(2 * nod, st, md);
    Build(2 * nod + 1, md + 1, dr);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}