Cod sursa(job #606666)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 august 2011 15:51:18
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <cstdio>

#define NMax 30005

using namespace std;

int N, ArbInt[4*NMax];

void Update (int K, int L, int R, int P, int V)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        ArbInt[K]=V;
        return;
    }
    if (P<=Mid)
    {
        Update (2*K, L, Mid, P, V);
    }
    else
    {
        Update (2*K+1, Mid+1, R, P, V);
    }
    ArbInt[K]=ArbInt[2*K]+ArbInt[2*K+1];
}

int Query (int K, int L, int R, int Q)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        return Mid;
    }
    if (ArbInt[2*K]<Q)
    {
        return Query (2*K+1, Mid+1, R, Q-ArbInt[2*K]);
    }
    return Query (2*K, L, Mid, Q);
}

int QuerySum (int K, int L, int R, int QL, int QR)
{
    int Mid=(L+R)/2;
    if (QL==L and QR==R)
    {
        return ArbInt[K];
    }
    if (QR<=Mid)
    {
        return QuerySum (2*K, L, Mid, QL, QR);
    }
    if (QL>Mid)
    {
        return QuerySum (2*K+1, Mid+1, R, QL, QR);
    }
    return QuerySum (2*K, L, Mid, QL, Mid)+QuerySum (2*K+1, Mid+1, R, Mid+1, QR);
}

int main()
{
    freopen ("order.in", "r", stdin);
    freopen ("order.out", "w", stdout);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        Update (1, 1, N, i, 1);
    }
    Update (1, 1, N, 2, 0);
    printf ("2 ");
    int P=2;
    for (int i=2; i<=N; ++i)
    {
        int X=(QuerySum (1, 1, N, 1, P)+i)%ArbInt[1];
        if (X==0)
        {
            X=ArbInt[1];
        }
        P=Query (1, 1, N, X);
        Update (1, 1, N, P, 0);
        printf ("%d ", P);
    }
    printf ("\n");
    return 0;
}