Cod sursa(job #2606423)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 27 aprilie 2020 18:42:41
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>
#define MAX 30000

using namespace std;

int n;
int aint[MAX * 4 + 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 desiredPoz, int st, int dr)
{
    if(dr <= desiredPoz)return aint[poz];

    int mij = (st + dr) >> 1;
    int leftValue, rightValue;

    leftValue = rightValue = 0;

    leftValue = query(poz << 1, desiredPoz, st, mij);
    if(mij < desiredPoz)rightValue = query((poz << 1) + 1, desiredPoz, mij + 1, dr);

    return leftValue + rightValue;
}

int query2(int poz, int st, int dr, int val)
{
    if(st == dr)
    {
        if(aint[poz] == val)return st;
        else return -1;
    }

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

    if(aint[poz << 1] >= val)return query2(poz << 1, st, mij, val);
    else return query2((poz << 1) + 1, mij + 1, dr, val - aint[poz << 1]);
}

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 dif = query(1, currPos, 1, n);
        int nextPos = query2(1, 1, n, i + dif);

        if(nextPos != -1)
        {
            fout << nextPos << " ";
            currPos = nextPos;
            update(1, nextPos, 1, n, 0);
        }
        else
        {
            int currSol = query(1, n, 1, n) - dif;
            int nextPos = query2(1, 1, n, i - currSol);

            fout << nextPos << " ";
            currPos = nextPos;
            update(1, nextPos, 1, n, 0);
        }

        i = newI;
        remained--;
    }

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

    return 0;
}