Cod sursa(job #780814)

Utilizator visanrVisan Radu visanr Data 21 august 2012 22:41:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define leftSon (node << 1)
#define rightSon ((node << 1) + 1)
#define nmax 30010

int Aint[4 * nmax], N, pos, K, aux, T;


void BuildTree(int node, int left, int right)
{
     if(left == right)
     {
             Aint[node] = 1;
             return ;
     }
     int mid = (left + right) >> 1;
     BuildTree(leftSon, left, mid);
     BuildTree(rightSon, mid + 1, right);
     Aint[node] = Aint[leftSon] + Aint[rightSon];
}

void Update(int node, int left, int right)
{
     if(left == right)
     {
             Aint[node] --;
             return ;
     }
     int mid = (left + right) >> 1;
     if(pos <= mid) Update(leftSon, left, mid);
     else Update(rightSon, mid + 1, right);
     Aint[node] = Aint[leftSon] + Aint[rightSon];
}

int Query(int node, int left, int right)
{
    if(left == right) return left;
    int mid = (left + right) >> 1;
    if(Aint[leftSon] >= aux) 
                     return Query(leftSon, left, mid);
    else
    {
        aux -= Aint[leftSon];
        return Query(rightSon, mid + 1, right);
    }
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    int i;
    scanf("%i", &N);
    BuildTree(1, 1, N);
    T = 1;
    for(i = 1; i <= N; i++)
    {
          T = (T + i) % Aint[1];
          if(!T) T = Aint[1];
          aux = T;
          pos = Query(1, 1, N);
          printf("%i ", pos);
          Update(1, 1, N);
          T --;
          if(!T) T = Aint[1];
    }
    return 0;
}