Cod sursa(job #2403587)

Utilizator MateiTrandafirMatei Trandafir MateiTrandafir Data 11 aprilie 2019 18:33:27
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>

int tree[1 << 17], n, a, b, r, x;

inline void update(int p, int st, int dr) {
    if (st == dr) {
        tree[p] = 1;
        r = st;
        return;
    }
    int m = (st + dr) / 2;
    int l = m - st + 1 - tree[2 * p];
    if (x <= l) update(2 * p, st, m);
    else {
        x -= l;
        update(2 * p + 1, m + 1, dr);
    }
    tree[p] = tree[2 * p] + tree[2 * p + 1];
}

inline void update() {
    update(1, 1, n);
}

inline int query(int p, int st, int dr) {
    if (a <= st && dr <= b) return dr - st + 1 - tree[p];
    int m = (st + dr) / 2, r1 = 0, r2 = 0;
    if (a <= m) r1 = query(2 * p, st, m);
    if (b > m) r2 = query(2 * p + 1, m + 1, dr);
    return r1 + r2;
}

inline int query() {
    return query(1, 1, n);
}

int main() {
    std::ifstream in("order.in");
    std::ofstream out("order.out");
    in >> n;
    b = n;
    int c = 2, q = 0, m = n;
    for (int pas = 1; pas <= n;) {
        x = c;
        update();
        --m;
        out << r << ' ';
        a = r + 1;
        if (a <= b) q = query();
        else q = 0;
        ++pas;
        if (pas <= q) c = c - 1 + pas;
        else if (m > 0) {
            c = (pas - q) % m;
            if (c == 0) c = m;
        }
    }
    return 0;
}