Cod sursa(job #1288784)

Utilizator Mihai_BogdanDumitru Mihai Mihai_Bogdan Data 9 decembrie 2014 05:35:00
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
#define MAXN 30005

int n,m,i,t,j,k,arb[4*MAXN],poz;
void init(int nod, int st, int dr) {
    if (st<dr) {
        arb[nod]=dr-st+1;
    }
    if (st==dr) arb[nod]=st;
    if (st<dr) {
        int mij=(st+dr)>>1;
        if (st<=mij) init(nod*2,st,mij);
        if (mij<dr) init(nod*2+1,mij+1,dr);
    }
}

int elim(int nod, int st, int dr, int poz) {
    if ( (st==dr)) {
        int rez=arb[nod];
        arb[nod]=0;
        return rez;
    }
    else if (st<dr) {
        arb[nod]--;
        int mij=(st+dr)>>1;
        int ls,ld;
        if ( (st==mij) && (arb[nod*2]>0) ) ls=1; else ls=arb[nod*2];
        if (dr==mij+1) ld=1; else ld=arb[nod*2+1];

        if (poz<=ls) return elim(nod*2,st,mij,poz);
        else if (mij+1<=dr)       return elim(nod*2+1,mij+1,dr,poz-ls);


    }
    return -1;
}

int main() {
    fin>>n;
    init(1,1,n);
    k=n;
    i=0;
    t=1;
    i=1;
    while (k>0) {
        i+=t;
        i%=k;
        if (i==0) i=k;
        m=elim(1,1,n,i);
        fout<<m<<" ";
        i--;
        k--;
        t++;
    }
    fout<<"\n";
    fout.close();
    return 0;
}