Cod sursa(job #1597654)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 12 februarie 2016 11:02:19
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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 )
    {
        poz = beg;
        //os << "\nsuma = " << Sum(1, 1, n);
        elim = ( Sum(1, 1, n) + i ) % ( n - i + 1);
        if ( !elim )
            ++elim;
        //os << "\n" << beg << " " << elim << "!\n";
        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 ( elim <= a[2 * nod] )
        Update(2 * nod, st, md);
    else
    {
        elim -= a[2 * nod];
        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];
}