Cod sursa(job #2605760)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 25 aprilie 2020 19:04:52
Problema Order Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <bits/stdc++.h>
#define MAX 30000

using namespace std;

int n;
int aint[MAX * 4 + 5];
bool scos[MAX + 5];

void update(int poz, int desiredPoz, int st, int dr, int val)
{
    if(st == dr)
    {
        aint[poz] = val;

        return;
    }

    int mij = (st + dr) >> 1;

    if(mij >= desiredPoz)update(poz << 1, desiredPoz, st, mij, val);
    else update((poz << 1) + 1, desiredPoz, mij + 1, dr, val);

    aint[poz] = aint[poz << 1] + aint[(poz << 1) + 1];
}

int query(int poz, int st, int dr, int left, int right)
{
    if(left <= st && dr <= right)return aint[poz];

    int mij = (st + dr) >> 1;
    int leftVal, rightVal;

    leftVal = rightVal = 0;

    if(mij >= left)leftVal = query(poz << 1, st, mij, left, right);
    if(mij < right)rightVal = query((poz << 1) + 1, mij + 1, dr, left, right);

    return leftVal + rightVal;
}

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++)
        update(1, i, 1, n, 1);

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

    int remained = n, currPos = 1;

    for(int i = 1; i <= n; i++)
    {
        int newI = i;
        i %= remained;

        if(!i)i = remained;

        int gasit = currPos;

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

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

            if(!gasit)gasit = n;
        }

        if(query(1, 1, n, currPos + 1, gasit) == i)
        {
            fout << gasit << " ";
            currPos = gasit;
            scos[gasit] = 1;
            update(1, gasit, 1, n, 0);
        }
        else
        {
            int currSol = query(1, 1, n, currPos, gasit);
            gasit = 0;

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

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

                if(!gasit)gasit = n;
            }

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

        i = newI;
        remained--;
    }

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

    return 0;
}