Cod sursa(job #2947208)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 25 noiembrie 2022 20:21:31
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 60004;

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

int n;
int nr_ramase;
struct BinaryIndexedTree
{
    vector<int> bit;
    void init()
    {
        bit.assign(n + 4, 0);
        for (int i = 1; i <= n; i++)
        {
            add(i, 1);
        }
    }

    void add(int idx, int value)
    {
        while (idx <= n)
        {
            bit[idx] += value;
            idx += (idx & (-idx));
        }
    }

    int sum(int idx)
    {
        int total = 0;
        while (idx > 0)
        {
            total += bit[idx];
            idx -= (idx & (-idx));
        }
        return total;
    }

    int range_sum(int left, int right)
    {
        return sum(right) - sum(left - 1);
    }

} BIT;

int main()
{
    fin >> n;
    BIT.init();
    int nrc = 1;
    nr_ramase = n;
    for (int i = 1; i <= n; i++)
    {
        int p = 1;
        int val = (nrc + (i % nr_ramase));
        if (val > nr_ramase)
        {
            val -= nr_ramase;
        }
        while (p < n)
        {
            p <<= 1;
        }
        int j = 0;
        nrc = val - 1;
        nr_ramase--;
        if (nrc < 1)
        {
            nrc += nr_ramase;
        }
        while (p)
        {
            if (j + p <= n && BIT.bit[j + p] < val)
            {
                val -= BIT.bit[j + p];
                j += p;
            }
            p >>= 1;
        }
        fout << j + 1 << ' ';
        BIT.add(j + 1, -1);
    }
    fin.close();
    fout.close();
    return 0;
}