Cod sursa(job #761418)

Utilizator vendettaSalajan Razvan vendetta Data 25 iunie 2012 22:22:03
Problema Order Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nmax 30005

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

int n, a[nmax];
struct{

    int cnt;

}arb[nmax*4];

void citeste(){

    f >> n;

}

void udpate(int nod, int st, int dr, int poz, int val){

    if (st == dr){
        if (val == -1) arb[nod].cnt = 1;
        return;
    }

    int mij = ( st + dr) / 2;
    if (poz <= mij) udpate(nod*2, st, mij, poz, val);
            else udpate(nod*2+1, mij+1, dr, poz, val);

    arb[nod].cnt = arb[nod*2].cnt + arb[nod*2+1].cnt;

}

int afla_pozitie(int nod, int st, int dr, int x){

    if (st == dr){
        return st;
    }
    int mij = (st + dr) / 2;
    if (mij - st + 1 -arb[nod*2].cnt >= x)
        return afla_pozitie(nod*2,st, mij, x);
    else return afla_pozitie(nod*2+1, mij+1, dr, x-mij+st-1+arb[nod*2].cnt);

}

void rezolva(){

    for(int i=1; i<=n; i++){
        a[i] = i;
    }
    a[2] = -1;
    udpate(1,1,n,2,-1);
    int poz = 2;
    g << 2 << " ";
    int s = 2;
    for(int i=2; i<=n-1; i++){
        int x = i % (n-i+1);
        int nou = poz + x - 1;
        if (nou > (n-i+1) ) nou = nou - (n-i+1);
        //cout << nou << "\n";
        int cpy = nou;
        nou = afla_pozitie(1, 1, n, nou);
        g << a[nou] << " ";
        s+=a[nou];
        a[nou] = -1;
        udpate(1,1,n,nou,-1);
        poz = cpy;
    }

    g << (((n*(n+1))/2 ) - s) << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

}