Cod sursa(job #1306343)

Utilizator rangerChihai Mihai ranger Data 30 decembrie 2014 21:13:44
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<fstream>


using namespace std;

const int N = 30010;

int arb[4*N],n,i,len;


void built(int nod, int l,  int r)
{
    if (l==r) arb[nod] = 1;
    else{
        int mij = (l + r) / 2;
        built(2*nod,l,mij);
        built(2*nod+1,mij+1,r);
        arb[nod] = arb[2*nod] + arb[2*nod+1];
    }
}

void update(int nod, int l, int r, int poz)
{
    if (l==r) arb[nod]--;
    else{
        int mij = (l + r)  / 2;
        if (poz<=mij)
            update(2*nod,l,mij,poz);
        else update(2*nod+1,mij+1,r,poz);
        arb[nod] = arb[2*nod] + arb[2*nod+1];
    }
}

int query(int nod, int l, int r, int a, int b)
{
    if (a==l && b==r) return arb[nod];

    int mij = (l + r) / 2;
    if (b<=mij) return  query(2*nod,l,mij,a,b);
    else if (a>mij) return  query(2*nod+1,mij+1,r,a,b);
    return  query(2*nod,l,mij,a,mij) + query(2*nod+1,mij+1,r,mij+1,b);
}

int main()
{
    ifstream cin("order.in");
    ofstream cout("order.out");

    cin >> n;

    built(1,1,n);
    update(1,1,n,2);
    cout << "2 ";

    len = 1; int poz = 3;

    for (i=1;i<n;i++)
    {

    len++; int ll = len;


        int io = query(1,1,n,poz,n);

        int left = poz, right = n;
        if (io<ll) {
            ll -= io;
            left=1;
            ll %= query(1,1,n,1,n);
            if (!ll) ll = query(1,1,n,1,n);
        }
                while (left<right){
            int mij=(left + right) / 2;
            int po = query(1,1,n,left,mij);
            if (po>=ll)right = mij;
            else ll -= po, left = mij+1;
        }
        cout<<left<<" ";
        poz = left + 1;
        if (poz==n+1) poz=1;
        update(1,1,n,left);
    }
    return  0;
}