Cod sursa(job #2433035)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 25 iunie 2019 18:07:05
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>
#define f(a) (a & -a)
using namespace std;
ifstream fin ("order.in");
ofstream fout ("order.out");
const int NMAX = 30003;
int AIB [NMAX], n, val = 2, I;
void UP (int I, int val){
    for (int i = I; i <= n; i += f (i))
        AIB [i] += val;
}
int Q (int I){
    int S = 0;
    for (int i = I; i >= 1; i -= f (i))
        S += AIB [i];
    return S;
}
int CB (int A){
    int st = 1, dr = n, med, val;
    while (st <= dr){
        med = (st + dr) / 2;
        val = Q (med);
        if (val < A)st = med + 1;
        else dr = med - 1;
    }
    return st;
}
int main (){
    fin >> n;
    for (int i = 1; i <= n; i ++)UP (i, 1);
    for (int i = 1; i <= n; i ++){
        val = (val + i - 2) % (n + 1 - i) + 1;
        I = CB (val);
        fout << I << ' ';
        UP (I, -1);
    }
    return 0;
}