Cod sursa(job #2606109)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 26 aprilie 2020 23:33:18
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>
#define MAX 30005
#define last_bit(i)(i & (-i))

using namespace std;

int n;
int aib[MAX];
bool scos[MAX];

int query(int x)
{
    int sol = 0;

    while(x)
    {
        sol += aib[x];
        x -= last_bit(x);
    }

    return sol;
}

void update(int x)
{
    while(x <= n)
    {
        aib[x]--;
        x += last_bit(x);
    }
}

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

    //ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);

    fin >> n;

    for(int i = 1; i <= n; i++)
        aib[i] = i - (i - last_bit(i));

    int p = 1;
    for(; (p << 1) <= n; p <<= 1);

    int remained = n, currPos = 1;

    for(int i = 1; i <= n; i++)
    {
        int copyI = i;
        i %= remained;
        if(!i)i = remained;

        int gasit = currPos;
        int dif = query(currPos);

        for(int j = p; j; j >>= 1)
            if(gasit + j <= n && query(gasit + j) - dif <= i)
                gasit += j;

        while(scos[gasit])
        {
            gasit--;

            if(!gasit)gasit = n;
        }

        if(query(gasit) - dif == i)
        {
            fout << gasit << " ";
            scos[gasit] = 1;
            update(gasit);
            currPos = gasit;
        }
        else
        {
            int solCurr = query(gasit) - dif;

            int gasit = 0;

            for(int j = p; j; j >>= 1)
                if(gasit + j <= currPos && query(gasit + j) + solCurr <= i)
                    gasit += j;

            while(scos[gasit])
            {
                gasit--;
                if(!gasit)gasit = n;
            }

            fout << gasit << " ";
            scos[gasit] = 1;
            update(gasit);
            currPos = gasit;
        }

        remained--;
        i = copyI;
    }

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

    return 0;
}