Cod sursa(job #1799994)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 7 noiembrie 2016 09:47:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 30005;

int tree[NMax * 4];

void buildTree(const int &node, const int &lo, const int &hi) {

    if(lo == hi) {
        tree[node] = 1;
        return;
    }

    int mid = ((lo + hi) >> 1);
    buildTree(node * 2, lo, mid);
    buildTree(node * 2 + 1, mid + 1, hi);

    tree[node] += tree[node * 2] + tree[node * 2 + 1];
}

void query(const int &node, const int &lo, const int &hi, int pos) {

    tree[node]--;
    if(lo == hi) {
        fout << lo << " ";
        return;
    }

    int mid = (lo + hi) >> 1;
    if(tree[node * 2] >= pos) {
        query(node * 2, lo, mid, pos);
    } else {
        query(node * 2 + 1, mid + 1, hi, pos - tree[node * 2]);
    }

}

int main() {

    ios::sync_with_stdio();
    fin.tie(NULL);

    int n;
    fin >> n;

    buildTree(1, 1, n);

    int cop = n;
    int pos = 1;
    for(int i = 1; i <= n; i++) {
        pos += i;
        pos = ((pos - 1) % cop) + 1;
        query(1, 1, n, pos);
        pos -= 1;
        cop--;
    }

    return 0;
}