Cod sursa(job #3218742)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 27 martie 2024 22:50:05
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");
int n, i, p, aib[30002], add;

static inline int Ub(int a) {
    return (a & -a);
}

static inline void Add(int poz, int val) {
    for(int i = poz; i <= n; i += Ub(i))
        aib[i] += val;
}

static inline int Sum(int poz) {
    int s = 0;
    for(int i = poz; i >= 1; i -= Ub(i)) s += aib[i];
    return s;
}

static inline int Cb(int val) {
    int st = 1, dr = n;
    int poz = n;
    while(st <= dr) {
        int mij = st + (dr - st) / 2;
        if(Sum(mij) >= val) {
            poz = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    return poz;
}

int main() {
    fin >> n;
    for(i = 1; i <= n; i++) Add(i, 1);

    p = 1;
    for(i = 1; i <= n; i++) {
        int poz = (i % (n - i + 1) + Sum(p)) % (n - i + 1);
        if(poz == 0) poz = n - i + 1;

        p = Cb(poz);
        fout << p << " ";
        Add(p, -1);
    }

    return 0;
}