Cod sursa(job #1007800)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 9 octombrie 2013 19:17:16
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>

#define maxn 30001

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int n,cnt,wh;
int arb[1<<17];

void create_tree (int node, int left, int right)
{
    if (left == right)
    {
        arb[node] = 1;
        return;
    }
    int mid = (left+right)/2;

    create_tree (node*2,left,mid);
    create_tree (node*2+1,mid+1,right);

    arb[node] = arb[node*2] + arb[node*2+1];
}

void update (int node, int left, int right)
{
    if (left == right)
    {
        arb[node] = 0;
        return;
    }
    int mid = (left+right)/2;

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

    arb[node] = arb[node*2] + arb[node*2+1];
}

void find (int node, int left, int right, int val)
{
    if (left == right)
    {
        wh = left;
        return;
    }

    int mid = (left+right)/2;

    if (val <= arb[node*2])
       find (node*2,left,mid,val);
    else
       find (node*2+1,mid+1,right,val-arb[node*2]);
}


int main()
{
    fin>>n;

    cnt = 1;

    create_tree(1,1,n);

    for (int i=1; i<=n; ++i)
    {
        cnt = (cnt+i-1)%(n-i+1) + 1;

        find (1,1,n,cnt);

        fout<<wh<<" ";

        update (1,1,n);
        --cnt;
    }
}