Cod sursa(job #2189163)

Utilizator theoioanaTheodoraD theoioana Data 27 martie 2018 19:44:52
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int const nmax = 30000;
int aib[nmax];
int n;

void update( int position, int value){
    for( ; position <= n; position += (position & -position)){
        aib[position] += value;
    }
}

int main(){

    fin >> n;

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

    int child = 2;
    int remaining_children = n;

    for( int i = 1; i <= n; i++){
        child = (child + i - 1) % remaining_children;
        if( child == 0 ){
            child = remaining_children;
        }
        --remaining_children;
        int left_pos = 0;
        int accmlate = 0;
        for( int j = 15 ; j >= 0; j--){
            if( left_pos + ( 1 << j) < n){
                if( accmlate + aib[left_pos + (1 << j)] < child){
                    accmlate += aib[left_pos + (1 << j)];
                    left_pos +=(1 << j);
                }
            }
        }
        left_pos++;
        update(left_pos, -1);
        fout << left_pos << " ";
    }

    return 0;
}