Cod sursa(job #1710688)

Utilizator cristina_borzaCristina Borza cristina_borza Data 29 mai 2016 17:04:33
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

#define NMAX 30005

using namespace std;

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

int aib[NMAX] , n , pos;

void update(int poz , int val){
    while(poz <= n){
        aib[poz] += val;
        poz += poz & (poz ^ (poz - 1)) ;
    }
}

int solve(int val) {
    int i , p = 0;
    for(i = 1 ; i <= n ; i <<= 1);
    while(i) {
        if(i + p <= n && aib[i + p] < val) {
            val -= aib[i + p];
            p += i;
        }
        i >>= 1;
    }
    return p + 1;
}

int main()
{
    f >> n;
    for(int i = 1 ; i <= n ; ++i) {
        update(i , 1);
    }

    update(2 , -1);
    g << 2 << ' ';

    pos = 2;
    for(int i = 2 ; i <= n ; ++i) {
        int r = n - i + 1;
        pos = (pos + i - 1) % r;

        if(pos == 0)
            pos = r;

        int el = solve(pos);
        g << el << " ";

        update(el , -1);
    }
    return 0;
}