Cod sursa(job #1556421)

Utilizator antanaAntonia Boca antana Data 24 decembrie 2015 19:48:42
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#define MAX 30000
using namespace std;
int arb[MAX*4+100], vc[MAX+1];
void update(int l1, int l2, int poz, int nod, int val)
{
    int mij;
    if(l1==l2)
        arb[nod]+=val;
    else
    {
        mij=(l1+l2)/2;
        if(poz<=mij) update(l1, mij, poz, nod*2, val);
        else update(mij+1, l2, poz, nod*2+1, val);
        arb[nod]=arb[nod*2]+arb[nod*2+1];
    }
}
int x;
void query(int st, int dr, int l1, int l2, int nod)
{
    int mij;
    if(l1>=st&&l2<=dr)
        x+=arb[nod];
    else
    {
        mij=(l1+l2)/2;
        if(dr>mij) query(st, dr, mij+1, l2, nod*2+1);
        if(st<=mij) query(st, dr, l1, mij, nod*2);
    }
}
int n;
int elem(int nrel)
{
    int l1, l2, mij, p;
    l1=1;
    l2=n;
    while(l1<=l2)
    {
        mij=(l1+l2)/2;
        x=0;
        query(1, mij, 1, n, 1);
        if(x==nrel)
        {
            if(vc[mij]!=-1)
                p=mij;
        }
        if(x<nrel)
            l1=mij+1;
        if(x>=nrel)
            l2=mij-1;
    }
    return p;
}
int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    int i, e, poz;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        update(1, n, i, 1, 1);
    poz=2;
    int ram=n;
    for(i=1;i<=n;i++)
    {
        e=elem(poz);
        printf("%d ", e);
        vc[e]=-1;
        ram--;
        update(1, n, e, 1, -1);
        poz+=i;
        if(ram!=0)
            poz%=ram;
        if(ram==1)
            poz=1;
        if(poz==0)
            poz=ram;
    }
    return 0;
}