Cod sursa(job #1903835)

Utilizator raulmuresanRaul Muresan raulmuresan Data 5 martie 2017 12:57:57
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 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) {

    //facem update deodata cu query-ul
    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() {
    int n;
    fin >> n;

    buildTree(1, 1, n);

    int cop = n;//nr de elevi ramasi
    int pos = 1;//pozitia curenta
    for(int i = 1; i <= n; i++) {
        pos += i;
        pos = ((pos - 1) % cop) + 1;
        //fout << pos << "\n";
        query(1, 1, n, pos);
        pos -= 1;
        cop--;
    }
    //fout <<"\n";
    for(int i = 1;i <= 2*n;i++)
    {
        //fout << tree[i]<<" ";
    }

    return 0;
}