Cod sursa(job #1832761)

Utilizator delta_wolfAndrei Stoica delta_wolf Data 20 decembrie 2016 21:56:53
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include<fstream>

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

const int NMax = 30005;
int n;
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()
{

    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;
}