Cod sursa(job #840589)

Utilizator stoicatheoFlirk Navok stoicatheo Data 22 decembrie 2012 21:53:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <iostream>
using namespace std;
const int MAX_N = 1 << 15;
ifstream fin("order.in");
ofstream fout("order.out");
int aib[MAX_N + 1];
int N;
void update(int , int);
int search(int);
int main() {
    fin >> N;
    for (int i = 1; i <= N; ++i) update(i, 1);
    int step = 2; 
    for (int i = 0; i < N; ++i) {
        step = (step + i - 1) % (N - i) + 1;
        int cut = search(step);
        fout << cut << ' ';
        update(cut, -1);
    }
    return 0;
}
 
void update(int pos, int val) {
    for (int i = pos; i <= N; i += (i & -i)) {
        aib[i] += val; 
    }
}
 
int search(int val) {
    int result = 0, x = 0;
    for (int i = MAX_N; i > 0; i /= 2) {
        if (x + i <= N) {
            if (aib[x + i] < val) {
                x += i;
                val -= aib[x];
            }
            if (val == aib[x + i]) {
                result = i + x;
            }
        }
    }
    return result;
}