Cod sursa(job #1996901)

Utilizator dragos231456Neghina Dragos dragos231456 Data 2 iulie 2017 22:22:55
Problema Order Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,arb[120005],pos,last=1,k;
bool ok=true,orr=true;

void skipout(int nod,int lt,int rt,int a,int b)
{
    if(a<=lt && rt<=b)
    {
        k+=arb[nod];
        return;
    }
    if(lt==rt) return;
    int md=(lt+rt)/2;
    if(md>=a) skipout(nod*2,lt,md,a,b);
    if(md<b) skipout(nod*2+1,md+1,rt,a,b);
    return;
}

void update(int nod,int lt,int rt,int pos)
{
    if(lt==rt)
    {
        arb[nod]=1;
        return;
    }
    int md=(lt+rt)/2;
    if(pos<=md) update(nod*2,lt,md,pos);
    else update(nod*2+1,md+1,rt,pos);

    arb[nod]=arb[nod*2]+arb[nod*2+1];
    return;
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        pos=last+i;
        if(pos>n) pos-=n;
        if(pos<=last) ok=false;
        else ok=true;
        while(pos!=last || (i==n && orr))
        {
            if(i==n) orr=false;
            if(ok) skipout(1,1,n,last+1,pos);
            else
            {
                skipout(1,1,n,last+1,n);
                skipout(1,1,n,1,pos);
            }

            last=pos;

            pos+=k;
            if(pos>n) pos-=n;

            if(pos<last) ok=false;
            else ok=true;
            k=0;
        }
        g<<pos<<' ';
        update(1,1,n,pos);
    }
    return 0;
}