Cod sursa(job #1306351)

Utilizator rangerChihai Mihai ranger Data 30 decembrie 2014 21:36:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>


using namespace std;

const int N = 30010;

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


void update(int  poz,int val)
{
    while (poz<=n)
        arb[poz]+=val,poz+=poz&-poz;
}

int sum(int poz)
{
    int s(0);
    while (poz>0)
        s+=arb[poz],poz-=poz&-poz;
    return s;
}

int query(int l, int r)
{
    return sum(r)-sum(l-1);
}



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

    cin >> n;


    for (i=1;i<=n;i++) update(i,1);

    update(2,-1);
    cout << "2 ";

    len = 1; int poz = 3;

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

    len++; int ll = len;


        int io = query(poz,n);

        int left = poz, right = n;
        if (io<ll) {
            ll -= io;
            left=1;
            ll %= query(1,n);
            if (!ll) ll = query(1,n);
        }
                while (left<right){
            int mij=(left + right) / 2;
            int po = query(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(left,-1);
    }
    return  0;
}