Cod sursa(job #1095066)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 30 ianuarie 2014 12:55:19
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <cstdio>
#define dmax 30005
using namespace std;

int v[4*dmax], sum, n, last;

void update(int va, int val, int st, int dr, int nod)
{
    if(st==dr)
        v[nod]+=va;
    else
    {
        int m=(st+dr)/2;
        if(val<=m)
            update(va, val, st, m, 2*nod);
        else update(va, val, m+1, dr, 2*nod+1);
        v[nod]=v[2*nod]+v[2*nod+1];
    }
}

void query(int k, int st, int dr, int nod)
{
    if(st==dr)
    {
        printf("%i%c", st, ' ');
        last=st;
        v[nod]=0;
    }
    else
    {
        int m=(st+dr)/2;

        if(sum+v[2*nod]>=k)
            query(k, st, m, 2*nod);
        else
        {
            sum+=v[2*nod];
            query(k, m+1, dr, 2*nod+1);
        }
        v[nod]=v[2*nod]+v[2*nod+1];
    }

}

int main()
{
    freopen("order.in", "r", stdin);
    scanf("%i", &n);

    for(int i=1; i<=n; i++)
        update(1,i,1,n,1);
last=1;
    for(int i=1;i<=n;i++)
    {
        sum=0;
        int k=last%(n-i+1);
        if(!k) k=n-i+1;
        query(k, 1, n, 1); // sterge elementul de pe poz k

    }
    //c_pop(1, 1);
printf("%c", '\n');
    return 0;
}