Cod sursa(job #1999233)

Utilizator dragos231456Neghina Dragos dragos231456 Data 10 iulie 2017 18:01:18
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,arb[120005],last,m,ex,k;

void build(int nod,int lt,int rt,int pos)
{
    if(lt==rt)
    {
         arb[nod]=1;
         return;
    }
    int md=(lt+rt)/2;
    if(pos<=md) build(nod*2,lt,md,pos);
    else build(nod*2+1,md+1,rt,pos);

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

void query1(int nod,int lt,int rt,int x,int y)
{
    if(x<=lt && rt<=y)
    {
        ex+=arb[nod];
        return;
    }
    if(lt==rt) return;
    int md=(lt+rt)/2;
    if(md>=x) query1(nod*2,lt,md,x,y);
    if(md<y) query1(nod*2+1,md+1,rt,x,y);
}

void query2(int nod,int lt,int rt)
{
    if(lt==rt)
    {
        last=lt;
        arb[nod]=0;
        return;
    }
    int md=(lt+rt)/2;
    if(arb[nod*2]>=k) query2(nod*2,lt,md);
    else
    {
        k-=arb[nod*2];
        query2(nod*2+1,md+1,rt);
    }

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

void afisare()
{
    int d=0;
    for(int i=1;i<=4;++i)
    {
        for(int j=1;j<=(1<<(i-1));++j)
        {
            ++d;
            cout<<arb[d]<<' ';
        }
        cout<<endl;
    }
}

int main()
{
    f>>n; m=n+1;
    for(int i=1;i<=n;++i) build(1,1,n,i);
    last=1;
    for(int i=1;i<=n;++i)
    {
        --m;
        ex=0; query1(1,1,n,1,last);
        k=ex+i;
        while(k>m) k-=m;
        query2(1,1,n);
        g<<last<<' ';
        //afisare();
    }
    return 0;
}