Cod sursa(job #2242014)

Utilizator gapdanPopescu George gapdan Data 17 septembrie 2018 16:25:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#define NMAX 200005

using namespace std;

int n, sol;
int A[NMAX];

ifstream f("order.in");
ofstream g("order.out");

void buildArb(int node, int st, int dr) {
    if (st == dr) {
        A[node] = 1;
        return;
    }
    int mij = (dr + st) / 2;
    buildArb(node * 2, st , mij);
    buildArb(node * 2 + 1, mij + 1, dr);
    A[node] = A[node * 2] + A[node * 2 + 1];
}

void query(int node, int st, int dr, int poz) {
    if (st == dr) {
        sol = st;
        return;
    }
    int mij = (st + dr) / 2;
    if (A[node * 2] >= poz) query(node * 2, st, mij, poz);
        else query(node * 2 + 1, mij + 1, dr, poz - A[node * 2]);
}

void update(int node, int st, int dr, int poz) {
    if (st == dr) {
        A[node] = 0;
        return;
    }
    int mij = (st + dr) / 2;
    if (poz <= mij) update(node * 2, st, mij, poz);
        else update(node * 2 + 1, mij + 1, dr, poz);
    A[node] = A[node * 2] + A[node * 2 + 1];
}

int main() {
    f >> n;
    buildArb(1, 1, n);
    int poz = 1;
    int nr = n;
    bool isFirst = 0;
    for (int i = 1; i <= n; ++i) {
        poz = (poz + i - isFirst) % nr;
        if (!poz) poz = nr;
        sol = 0;
        query(1, 1, n, poz);
        update(1, 1, n, sol);
        g << sol << " ";
        isFirst = 1;
        --nr;
    }
    return 0;
}