Cod sursa(job #1208249)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 15 iulie 2014 11:43:35
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
using namespace std;

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

int N, x, y, X;
int Arb[4*30001];

void Build(int node, int left, int right);
void Update(int node, int left, int right);

int main()
{
    is >> N;
    for ( int i = 1; i <= N; ++i )
    {
        x = i;
        Build(1,1,N);
    }
    y = 1;
    X = N;
    for ( int i = 1; i <= N; ++i )
    {
        y += i;
        if ( i != 1 )
            y -= 1;
        if ( y > X )   y %= X;
        x = y;
        if ( y == 0 )
        {
            y = X;
            x = y;
        }
        if ( i == N )
        {
            x = 1;
            y = 1;
        }
        Update(1,1,N);
    }
}

void Build(int node, int left, int right)
{
    if ( left == right )
    {
        Arb[node] = 1;
        return;
    }

    int mid = (left+right)/2;

    if ( x <= mid ) Build(2*node,left,mid);
    else    Build(2*node+1,mid+1,right);

    Arb[node] = Arb[node*2] + Arb[node*2+1];

}

void Update(int node, int left, int right)
{
    if ( left == right )
    {
        os << left << " ";
        Arb[node] = 0;
        return;
    }

    int mid = (left+right)/2;

    if ( x <= Arb[node*2] ) Update(node*2,left,mid);
    else
    {
        x -= Arb[node*2];
        Update(node*2+1,mid+1,right);
    }

    Arb[node] = Arb[node*2] + Arb[node*2+1];
    X = Arb[node];
}