Cod sursa(job #2404548)

Utilizator MateiTrandafirMatei Trandafir MateiTrandafir Data 13 aprilie 2019 00:13:31
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>

int tree[1 << 16], n;

int a, b;

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(int left, int right) {
    a = left;
    b = right;
    return query(1, 1, n);
}

int x, r;

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 int update(int pos) {
    x = pos;
    update(1, 1, n);
    return r;
}

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