Cod sursa(job #829252)

Utilizator IoannaPandele Ioana Ioanna Data 4 decembrie 2012 23:08:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#define NMAX (1<<16)
using namespace std;

int n;
int v[NMAX];
int a,s;

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

void scan()
{
    in>>n;
}


void addToTree(int st,int dr,int k)
{
    if (st==dr)
    {
        v[k]=1;
        return;
    }
    int mij=(st+dr)/2;
    if (a<=mij)
        addToTree(st,mij,(k<<1));
    else addToTree(mij+1,dr,(k<<1)+1);
    v[k]=v[(k<<1)]+v[(k<<1)+1];
}


void build()
{
    for (int i=1;i<=n;i++)
    {
        a=i;
        addToTree(1,n,1);
    }
}

void elim(int k,int st,int dr)
{
    if (st==dr)
    {
        v[k]=0;
        out<<st<<" ";
        return;
    }
    int mij=(st+dr)/2,fs,fd;
    fs=2*k;
    fd=fs+1;
    if (v[fs]>=a)
    {
        elim(fs,st,mij);
        v[k]--;
    }
    else
    {
        a-=v[fs];
        elim(fd,mij+1,dr);
        v[k]--;
        s=s+v[k]-v[fd];
    }
}

void solve()
{
    int i=1,q;
    s=1;
    while (v[1])
    {
        a=(s+i)%v[1];
        if (!a)
            a=v[1];
        s=0;
        elim(1,1,n);
        i++;
    }
}
int main()
{
    scan();
    build();
    solve();
    return 0;
}