Cod sursa(job #2290218)

Utilizator max945Maxim C max945 Data 25 noiembrie 2018 23:50:32
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

#define nmax 30005

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

int n, pn, pv, nl;
int t[4*nmax+1];

void build(int nd, int lt, int rt) {
    if (lt == rt) {
        t[nd] = 1;
        return;
    }
    int mid = (lt + rt) / 2;
    build(2*nd, lt, mid);
    build(2*nd + 1, mid + 1, rt);
    t[nd] = t[2*nd] + t[2*nd + 1];
}

int query(int nd, int lt, int rt, int poz) {
    t[nd]--;
    if (lt == rt) {
        return lt;
    } else {
        int mid = (lt + rt) / 2;
        if (poz <= t[2*nd]) {
            return query(2*nd, lt, mid, poz);
        } else {
            return query(2*nd + 1, mid + 1, rt, poz - t[2*nd]);
        }
    }
}

int main() {
    fin >> n;
    build(1, 1, n);

    pv = 2;
    for (int i = 1; i <= n; i++) {
        pn = t[1];
        nl = (pv + i - 1) % pn;
        if (nl == 0) {nl = pn;}
        fout << query(1, 1, n, nl) << " ";
        pv = nl;
    }
    return 0;
}