Cod sursa(job #1148186)

Utilizator ThomasFMI Suditu Thomas Thomas Data 20 martie 2014 16:03:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
using namespace std;

#define NMax 30005
#define AMax 4*NMax

ifstream f("order.in");
ofstream g("order.out");

int n,start=1;
int val,lim1,lim2,ok,stop;
int A[AMax];

void arbp_verif(int nod,int st,int dr,int a,int b)
{
    if(stop==1) return;

    if(a<=st && dr<=b)
    {
        int cap=dr-st+1-A[nod];
        if(cap>=val) {lim1=st;lim2=dr;ok=1;stop=1;return;}
        else val-=cap;
    }
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij) arbp_verif(nod*2,st,mij,a,b);
        if(b>mij) arbp_verif(nod*2+1,mij+1,dr,a,b);
    }
}

void arb_search(int nod,int st,int dr)
{
    A[nod]++;

    if(st==dr)
    {
        start=st;
        return;
    }

    int mij=(st+dr)/2;
    int fiu1=nod*2,fiu2=nod*2+1;
    int cap=mij-st+1;

    if(cap-A[fiu1]>=val) arb_search(fiu1,st,mij);
    else
    {
        val-=cap-A[fiu1];
        arb_search(fiu2,mij+1,dr);
    }
}

void arbp_search(int nod,int st,int dr,int a,int b)
{
    A[nod]++;

    if(a<=st && dr<=b)
    {
        A[nod]--;
        arb_search(nod,st,dr);
        return;
    }
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij) arbp_search(nod*2,st,mij,a,b);
        if(b>mij) arbp_search(nod*2+1,mij+1,dr,a,b);
    }
}

int main()
{
    int i=0;

    f>>n;

    while(A[1]<n)
    {
        val=++i;
        ok=0;
        stop=0;
        arbp_verif(1,1,n,start+1,n);

        if(ok==1)
        {
            arbp_search(1,1,n,lim1,lim2);
        }
        else
        {
            val=val%(n-A[1]);
            if(val==0) val=n-A[1];
            arb_search(1,1,n);
        }

        g<<start<<" ";
    }

    g<<"\n";

    f.close();
    g.close();
    return 0;
}