Cod sursa(job #1034412)

Utilizator LizzardStanbeca Theodor-Ionut Lizzard Data 17 noiembrie 2013 20:15:18
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
using namespace std;

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

void clear(int , int , int , int , int &);
int get(int, int , int , int , int );
int build(int , int , int );
int n,v[100000];

int main()
{
    int i,poz,t,m,x;

    fin>>n;
    v[1]=build(1,n,1);

    for(i=1,t=1,m=n;i<=n;i++)
    {
        if(i==1)    poz=2;
        else poz=i;
        x=get(1,n,1,t,n);
        if(poz<=x)
        {
            poz+=get(1,n,1,1,t-1);
            clear(1,n,1,poz,t);
            v[1]--;
        }
        else
        {
            poz-=x;
            if(m!=1)
                poz%=m;
            else
                poz=1;
            clear(1,n,1,poz,t);
            v[1]--;
        }
        m--;
        fout<<t<<" ";
    }

    return 0;
}

void clear(int li, int ls, int i, int d, int &r)
{
    if(li==ls)
    {
        r=li;
        return;
    }

    int mij=(li+ls)/2;
    if(d>v[2*i])
    {
        v[2*i+1]--;
        clear(mij+1,ls,2*i+1,d-v[2*i],r);
    }
    else
    {
        v[2*i]--;
        clear(li,mij,2*i,d,r);
    }
    return;
}


int get(int li, int ls, int i, int ci, int cs)
{
    if(ci<=li && ls<=cs)
        return v[i];

    int mi=li,ms=ls;
    if(mi<ci)   mi=ci;
    if(ms>cs)   ms=cs;

    if(mi<=ms)
        return (get(li,(li+ls)/2,2*i,ci,cs)+get((li+ls)/2+1,ls,2*i+1,ci,cs));
    return 0;
}

int build(int li, int ls, int i)
{
    if(li==ls)
        v[i]=1;
    else
        v[i]=build(li,(li+ls)/2,2*i)+build((li+ls)/2+1,ls,2*i+1);
    return v[i];
}