Cod sursa(job #1095157)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 30 ianuarie 2014 15:11:55
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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];
    }
}

int tree_sum(int a, int b, int st, int dr, int nod)
{ int asd=0;
    if(a<=st && b>=dr)
        return v[nod];
    else
    {
        int m=(st+dr)/2;
        if(a<=m) asd=tree_sum(a,b,st,m, 2*nod);
        if(b>m) asd+=tree_sum(a,b,m+1,dr, 2*nod+1);
return asd;
    }
}

void query(int k, int st, int dr, int nod)
{
    if(st==dr)
    {
        printf("%i%c", st, ' ');
        last=st;
        v[nod]=0;
    }
else
{
    //k=tree_sum(1,st,1,n,1)+k;
        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);
    freopen("order.out", "w", stdout);
    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=(tree_sum(1, last, 1, n, 1)+i)%(n-i+1);
       if(!k) k=n-i+1;
//    /    if(t)// daca trece de capat
    query(k, 1, n, 1); // sterge elementul de pe poz k

    }
    //c_pop(1, 1);

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