Cod sursa(job #1792171)

Utilizator borcanirobertBorcani Robert borcanirobert Data 30 octombrie 2016 09:43:50
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
using namespace std;

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

const int MAXN = 30005;
int N;
int aib[MAXN];
int poz;

void Update( int p, int x );
int Sum( int p );

int main()
{
    int i, j, st, dr, mij;

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

    poz = 2;
    for ( i = 1; i <= N; i++ )
    {
        poz = ( poz + i - 1 ) % ( N - i + 1 );
        if ( poz == 0 ) poz = N - i + 1;

        st = 1, dr = N;
        while ( st <= dr )
        {
            mij = ( st + dr ) / 2;

            if ( Sum(mij) >= poz )
            {
                if ( Sum(mij) == poz )
                {
                    j = mij;
                }

                dr = mij - 1;
            }
            else
                st = mij + 1;
        }

        Update(j, -1);

        fout << j << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}

void Update( int p, int x )
{
    for ( int i = p; i <= N; i += i & -i )
        aib[i] += x;
}

int Sum( int p )
{
    int s = 0;

    for ( int i = p; i >= 1; i -= i & -i )
        s += aib[i];

    return s;
}