Cod sursa(job #1434708)

Utilizator theprdvtheprdv theprdv Data 11 mai 2015 10:29:34
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
using namespace std;

fstream fin("order.in", ios::in);
fstream fout("order.out", ios::out);
#define MAXN 30005
int T[4 * MAXN + 10], N, val, pos = 2;

void build(int node, int l, int r)
{
    if(l == r) { T[node] = 1; return; }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    T[node] = T[node * 2] + T[node * 2 + 1];
}
void update(int node, int l, int r)
{
    if(l == r) { T[node] = 0; pos = l; return; }
    int mid = (l + r) / 2;
    if(T[node * 2] >= val) update(node * 2, l, mid);
    else val -= T[node * 2], update(node * 2 + 1, mid + 1, r);
    T[node] = T[node * 2 + 1] + T[node * 2];
}
int main()
{
    fin >> N;
    build(1, 1, N);
    for(int i = 1; i <= N; ++i){
        val = pos;
        val += i - 1;
        val %= T[1] + 1;
        if(!val) ++val;
        update(1, 1, N);
        fout << pos << " ";
    }

    fin.close();
    fout.close();
    return 0;
}