Cod sursa(job #2470076)

Utilizator deiubejanAndrei Bejan deiubejan Data 8 octombrie 2019 17:55:01
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <bits/stdc++.h>
using namespace std;


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


#define cin fin
#define cout fout
/*
*/

const int MAXN=4e4;
int n;
int arbore[MAXN*4];
int kEl, erasedEl, findEl;


void build(int left, int right, int nod)
{
    arbore[nod]=right-left+1;
    if(left==right)
        return;

    int mij=(left+right)/2;
    build(left, mij, nod*2);
    build(mij+1, right, nod*2+1);
}

void query(int &kEl, int intLeft, int intRight, int left, int right, int nod)
{
    if(intLeft<=left&&right<=intRight)
    {
        kEl+=arbore[nod];
        return;
    }

    int mij=(left+right)/2;
    if(intLeft<=mij)
        query(kEl, intLeft, intRight, left, mij, 2*nod);
    if(mij<intRight)
        query(kEl, intLeft, intRight, mij+1, right, 2*nod+1);
}

/*
void update(int left, int right, int nod)
{
    arbore[nod]--;
    if(left==right)
    {
        el=left;
        return;
    }

    int mij=(left+right)/2;
    if(pos<=mij)
        update(left, mij, 2*nod);
    else
        update(mij+1, right, 2*nod+1);
}
*/

void update(int &erasedEl, int kleaEl, int left, int right, int nod)
{
    arbore[nod]--;
    if(left==right)
    {
        erasedEl=left;
        return;
    }

    int mij=(left+right)/2;
    if(arbore[nod*2]>=kleaEl)
        update(erasedEl, kleaEl, left, mij, nod*2);
    else
    {
        kleaEl-=arbore[nod*2];
        update(erasedEl, kleaEl, mij+1, right, nod*2+1);
    }
}



void print(int v[])
{
    for(int i=1; i<=2*n; i++)
        cout<<v[i]<<" ";
}




int main()
{
    cin>>n;
    build(1,n,1);
    erasedEl=1;
    for(int i=1; i<=n; i++)
    {
        kEl=0;
        findEl=i;
        query(kEl, erasedEl+1, n, 1, n, 1);

        if(kEl<findEl)
        {
            findEl-=kEl;
            kEl=0;
            query(kEl, 1, n, 1, n, 1);
            findEl%=kEl;
            if(findEl==0)
                findEl=kEl;
            update(erasedEl, findEl, 1, n, 1);
        }
        else
        {
            kEl=0;
            query(kEl, 1, erasedEl, 1, n, 1);
            findEl+=kEl;
            update(erasedEl, findEl, 1, n, 1);
        }
        cout<<erasedEl<<" ";
    }

    return 0;
}