Cod sursa(job #2590545)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 28 martie 2020 13:05:44
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>

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

const int NMAX = 30000;

int NR;

class BinTree {
    private :
        int N;
        int v[1 + NMAX];
        int aib[1 + NMAX];
    public :
        BinTree();
        ~BinTree(){};
        void update ( int poz, int val );
        int query ( int poz );
        int search ( int start, int val );
};

BinTree::BinTree ( ) {
    fin >> N;
    NR = N;
    for ( int i = 1; i <= N; ++i ) {
        v[i] = 1;
        update ( i, v[i] );
    }
}

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

int BinTree::query ( int poz ) {
    int ans = 0;
    while ( poz ) {
        ans += aib[poz];
        poz = poz - ( poz & ( poz - 1 ) ^ poz );
    }
    return ans;
}

int BinTree::search ( int start, int val ) {
    int sum = query ( N ) - query ( start );
    if ( sum < val )
        return search ( 0, val - sum );
    int pas = 1<<16;
    int ans = start;
    while ( pas ) {
        if ( ans + pas <= N && query ( ans + pas ) - query ( start ) < val )
            ans += pas;
        pas /= 2;
    }
    return ans + 1;
}

int main() {

    BinTree arbore = BinTree();

    int start = 1;

    for ( int i = 1; i <= NR; ++i ) {
        start = arbore.search ( start, i % ( NR - i + 1 ) );
        fout << start << ' ';
        arbore.update ( start, -1 );
    }

    fin.close();
    fout.close();

    return 0;
}