Cod sursa(job #2290222)

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

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");
	
int n;
int tree[120001];
	
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, 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;
}