Cod sursa(job #1525025)

Utilizator andreiudilaUdila Andrei andreiudila Data 14 noiembrie 2015 17:36:36
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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,next;
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 l, int r, int nr)
{
    int mid=(l+r)/2;
    int l1=l;

    while(l<=r)
    {
        mid=(l+r)/2;
        suma=0;
        x=l1;
        y=mid;

        query(1,1,n);

        if(suma>=nr) r=mid-1;
        else l=mid+1;
    }

    return l;
}
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)
        {
            next=cauta(xc, n, k);
            xc=next;
            ++kg;
        }
        else
        {
            int k1=k-suma;
            next=cauta(1, xc, k1);

            xc=next;
            ++kg;
        }

    }

    return 0;
}