Cod sursa(job #1390603)

Utilizator irimiecIrimie Catalin irimiec Data 17 martie 2015 10:33:38
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#define MAXN 31000

#ifndef ONLINE_JUDGE
ifstream f("order.in");
ofstream g("order.out");
#endif

int n, pos;
int Aint[8 * MAXN];

void buildTree(int nod, int l, int r) {
    if(l == r) {
        Aint[nod] = 1;
        return;
    }

    int mid = (l + r) >> 1;
    if(mid >= l)
        buildTree( (nod << 1), l, mid );
    if(mid < r)
        buildTree( (nod << 1) + 1, mid + 1, r);
    Aint[nod] = Aint[ (nod << 1) ] + Aint[ (nod << 1) + 1 ];
}

int updateTree(int nod, int l, int r, int v) {
    Aint[nod]--;
    if(l == r) {
        return l;
    }

    int mid = (l + r) >> 1;
    if(v <= Aint[(nod << 1)])
        return updateTree((nod << 1), l, mid, v);
    else
        return updateTree((nod << 1) + 1, mid + 1, r, v - Aint[(nod << 1)]);
}

int main() {
    f >> n;
    buildTree(1, 1, n);
    int pos = 1;
    for(int i = 1; i <= n; ++i) {
        pos = (pos + i) % Aint[1];
        //cout << pos << " ";
        if(!pos)
            pos = Aint[1];
        g << updateTree(1, 1, n, pos) << " ";
        pos--;
    }
    return 0;
}