Cod sursa(job #2754906)

Utilizator MadalinaKopaczMadalina Kopacz MadalinaKopacz Data 26 mai 2021 17:51:37
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
using namespace std;

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

int n;
int AINT[200005];
//https://www.geeksforgeeks.org/interval-tree/
void Update(int nod, int st, int dr, int poz)
{
    if (st == dr)
    {
        AINT[nod] = 0;
        return;
    }
    int mij = (st + dr) / 2;
    if (poz <= mij)
        Update(nod * 2, st, mij, poz);
    else
        Update(nod * 2 + 1, mij + 1, dr, poz);
    AINT[nod] = AINT[nod * 2] + AINT[nod * 2 + 1];
}

int Query(int nod, int st, int dr, int k)
{
    if (st == dr) return st;
    int mij = (st + dr) / 2;
    if (AINT[2 * nod] >= k)
        return Query(2 * nod, st, mij, k);
    else
        return Query(2 * nod + 1, mij + 1, dr, k - AINT[2 * nod]);
}

void Build(int nod, int st, int dr)
{
    if (st == dr)
    {
        AINT[nod] = 1;
        return;
    }
    int mij = (st + dr) / 2;
    Build(2 * nod, st, mij);
    Build(2 * nod + 1, mij + 1, dr);
    AINT[nod] = AINT[2 * nod] + AINT[2 * nod + 1];
}

int main()
{
    fin >> n;
    Build(1, 1, n);
    int poz = 2;
    for (int i = 1; i <= n; i++)
    {
        poz += (i - 1);
        while (poz > AINT[1])
            poz -= AINT[1];
        int q = Query(1, 1, n, poz);
        fout << q << " ";
        Update(1, 1, n, q);
    }
    return 0;
}