Cod sursa(job #3168114)

Utilizator andreipirjol5Andrei Pirjol andreipirjol5 Data 11 noiembrie 2023 16:14:28
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

vector <int> aint;
int rightmax, n;
void get_values()
{
    int exp = log2(n), nodes;

    if((1 << exp) != n)
        exp++;

    nodes = 2 * (1 << exp) - 1;
    rightmax = 1 << exp;

    aint.reserve(nodes + 5);
}

void build(int node = 1, int left = 1, int right = rightmax)
{
    if(left == right and left > n)
    {
        aint[node] = 0;
        return;
    }

    if(left == right)
    {
        aint[node] = 1;
        return;
    }

    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);

    aint[node] = aint[2 * node] + aint[2 * node + 1];
}

void update(int value, int node = 1, int left = 1, int right = rightmax)
{
    if(left == right and left > n)
    {
        aint[node] = 0;
        return;
    }

    if(left == right)
    {
        aint[node] = 0;
        fout << left << ' ';
        return;
    }

    int mid = (left + right) / 2;

    if(value <= aint[2 * node])
        update(value, 2 * node, left, mid);
    else update(value, 2 * node + 1, mid + 1, right);

    aint[node]--;
}

int main()
{
    fin >> n;
    int available = n;
    get_values();

    build();

    int curr = 2;

    for(int i = 1; i <= n; i++)
    {
        curr = (i + curr - 1) % available;
        if(curr == 0)
            curr = available;

        update(curr);

        available--;
    }

    return 0;
}