Cod sursa(job #2290214)

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

using namespace std;

#define nmax 30005

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

int n;
int tree[4*nmax+1];

void build(int node, int left, int right) {
    if (left == right) {
        tree[node] = 1;
        return;
    }
    int mid = (left + right) / 2;
    build(2*node, left, mid);
    build(2*node + 1, mid + 1, right);
    tree[node] = tree[2*node] + tree[2*node + 1];
}

int query(int node, int left, int right, int person) {
    tree[node]--;
    if (left == right) {
        return left;
    } else {
        int mid = (left + right) / 2;
        if (person <= tree[2*node]) {
            return query(2*node, left, mid, person);
        } else {
            return query(2*node + 1, mid + 1, right, person - tree[2*node]);
        }
    }
}

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

    int personsNum = n, prevLoser = 2;
    for (int skip = 1; skip <= n; skip++) {
        personsNum = tree[1];
        int nextLoser = (prevLoser + skip - 1) % personsNum;
        if (nextLoser == 0) {nextLoser = personsNum;}
        fout << query(1, 1, n, nextLoser) << " ";
        prevLoser = nextLoser;
    }
    return 0;
}