Cod sursa(job #950565)

Utilizator darrenRares Buhai darren Data 17 mai 2013 10:20:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;

int N, P;
int AIB[30002];

void update(int pos)
{
    for (; pos <= N; pos += pos & -pos)
        ++AIB[pos];
}
int query(int pos)
{
    int sum = 0;
    for (; pos >= 1; pos -= pos & -pos)
        sum += AIB[pos];
    return sum;
}

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

    fin >> N;
    P = 1;

    for (int i = 1; i <= N; ++i) // caut al i-lea
    {
        int pas = i % (N - i + 1);
        if (pas == 0) pas = N - i + 1;

        if (N - P - (query(N) - query(P)) >= pas)
        {
            int step = 1 << 14, resnow;
            for (resnow = P - 1; step; step >>= 1)
                if (resnow + step <= N && (resnow + step) - P - (query(resnow + step) - query(P)) < pas)
                    resnow += step;
            ++resnow;

            P = resnow;
        }
        else
        {
            int sub = pas - (N - P - (query(N) - query(P)));

            int step = 1 << 14, resnow;
            for (resnow = 0; step; step >>= 1)
                if (resnow + step <= N && (resnow + step) - query(resnow + step) < sub)
                    resnow += step;
            ++resnow;

            P = resnow;
        }

        fout << P << ' ';
        update(P);
    }

    fout << '\n';

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