Cod sursa(job #2748463)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 30 aprilie 2021 19:42:18
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 30001;

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

int AIB[NMAX], N;

void Update( int pos, int val ){

    while( pos <= N)
    {
        AIB[pos] += val;
        pos += ( pos & -pos );
    }
}

int Query( int pos ){

    int sum = 0;
    while( pos )
    {
        sum += AIB[pos];
        pos -= ( pos & -pos );
    }
    return sum;
}

int BS( int lf, int rg, int val ){
    if( lf > rg )
        return 200000000;

    int mid = lf + ( rg - lf ) / 2;

    //cout << lf << ' ' << rg << ' ' << mid << ' ' << Query( mid ) << '\n';

    if( Query( mid ) > val )
        return  BS( lf, mid-1, val );
    if( Query( mid ) < val )
       return BS( mid+1, rg, val );

    return min( mid, BS( lf, mid-1, val ) );
}
int main()
{
    fin >> N;

    for( int i = 1; i <= N; ++i )
        Update( i, 1 );

    int index = 1;
    int val, end_sum;

    for( int i = 1; i <= N; ++i )
    {
        val = i;
        //cout << Query(N) << '-' << Query(index) << '\n';
        end_sum = Query(N) - Query(index);

        //cout << val << '\n';

        if(  end_sum < val )
        {
            //cout << end_sum << ":\n";
            val -= end_sum;

            index = 0;

            end_sum = Query(N);
            val = val % end_sum;

            if( !val ) val = end_sum;
        }
        //cout << val << '+' << Query(index) << '\n';
        index = BS( index+1, N, val + Query(index) );
        Update( index, -1 );
        //cout << index << '\n';
        fout << index << ' ';
    }
}