Cod sursa(job #1372511)

Utilizator AeroHHorea Stefan AeroH Data 4 martie 2015 13:54:19
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define punct pair<double,double>
#define inf 123456789
using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int N,aib[60002],fv[60002],i,pos,S,ok;

int Q(int pos)
    {
        if (pos<0)return 0;
        int t=0,i;
        for (i=pos;i;i-=i&(-i))
            t+=aib[i];
        return t;
    }

void U(int pos)
    {
        int i;
        for (i=pos;i<=2*N;i+=i&(-i))
            --aib[i];
    }
void B(int x)
    {
        if (x == 0)
        {
            if(!ok)
            pos--;
            return;
        }
        int i,s=S;
        for(i=0;s;s>>=1)
            if (pos + i + s + 1 < 2*N && (Q(pos+i+s+1) - Q(pos+1) < x))
                i+=s;
        pos =((pos + i + 1)%N);
    }
void F()
{
    int i,s=S;
    for(i=0;s;s>>=1)
        if (pos + i + s + 1 < 2*N && (Q(pos+i+s ) - Q(pos - 1) < 1))
            i+=s;

    if (Q(pos)-Q(pos-1) == 0)
        {
            pos=pos+i;
            ok++;
        }
}

int main()
{
    f>>N;
    S=log2(N),S=1<<(S+3);

    for (i=0;i<=N*2;++i)
        aib[i]=i&(-i);

    for (i=1;i<N;++i)
    {
        B((i-ok)%(N-i+1));
        pos%=N;
        U(pos+1);
        U(pos+1+N);
        g<<pos+1<<" ";
        //fv[pos+1]++;
        ok=0;
        F();
    }
    for (i=1;i<=N;++i)
        if (aib[i])
    {
        g<<i;
        //++fv[i];
        break;
    }


    /*for(i=1;i<=N;++i)
        if (fv[i]==0)
            g<<i<<'\n';*/

    return 0;
}