Cod sursa(job #2589662)

Utilizator copanelTudor Roman copanel Data 26 martie 2020 18:05:37
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>

const int L = 15;
int aib[30001];

constexpr int LSB(int n) {
    return n & (-n);
}

int cauta(int n, int x) {
    int p = 0, pas = 1 << L;
    while (pas != 0) {
        if (p + pas <= n && aib[p + pas] < x) {
            p += pas;
            x -= aib[p];
        }
        pas >>= 1;
    }
    return p + 1;
}

void update(int n, int p, int val) {
    while (p <= n) {
        aib[p] += val;
        p += LSB(p);
    }
}

int main() {
    std::ifstream fin("order.in");
    std::ofstream fout("order.out");
    int n, remaining;

    fin >> n;
    for (int i = 1; i <= n; i++) {
        update(n, i, 1);
    }

    remaining = n;
    int pos = 1;
    for (int i = 1; i <= n; i++) {
        pos = (pos + i) % remaining;
        if (pos == 0) {
            pos = remaining;
        }

        int de_taiat = cauta(n, pos);
        fout << de_taiat << ' ';

        update(n, de_taiat, -1);
        remaining--;
        pos--;
    }
    return 0;
}