Cod sursa(job #1525040)

Utilizator andreiudilaUdila Andrei andreiudila Data 14 noiembrie 2015 17:48:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
using namespace std;

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


int n,i,aux, poz,val,x,y, m, op,suma=0,nextt;
int aint[120010];


void update(int nod, int l, int r)
{
    if(l==r) aint[nod]+=val;
    else
    {
        int mid=(l+r)/2;
        if(poz<=mid) update(2*nod,l, mid);
            else update(2*nod+1, mid+1, r);

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


}



void query(int nod, int l, int r)
{
    if(l>=x && r<=y) suma+=aint[nod];
    else
    {
        int mid=(l+r)/2;

     if(x<=mid) query(2*nod, l, mid);
     if(y>mid) query(2*nod+1, mid+1, r);
}
}

int cauta(int nod, int l, int r, int nr){

   if (l==r) return l;
   else {
     int mid=(l+r)/2;

     if (aint[2*nod]>=nr) return cauta(2*nod,l,mid,nr);
     else return cauta(2*nod+1,mid+1,r,nr-aint[2*nod]);

   }

}

int main()
{
     fin>>n;
    val=1;
    for (int i=1; i<=n; ++i)
    {
        poz=i;
        update(1,1,n);
    }

    int xc=2, nr=n,kg=2, k;

    while(nr>0)
    {
        val=-1;
        poz=xc;
        update(1,1,n);
        --nr;
        fout<<xc<<" ";

        if (nr==0) break;

        suma=0;

        x=xc;
        y=n;

        query(1,1,n);

        k=kg%nr;

        if (k==0) k=nr;

        if(suma>=k)
        {
            suma=0;
            x=1;
            y=xc;
            query(1,1,n);

            nextt=cauta(1,1,n,k+suma);
            xc=nextt;
            ++kg;
        }
        else
        {
            int k1=k-suma;
            nextt=cauta(1,1,n,k1);

            xc=nextt;
            ++kg;
        }

    }

    return 0;
}