Cod sursa(job #2289690)

Utilizator Constantin.Dragancea Constantin Constantin. Data 25 noiembrie 2018 00:17:12
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 30010;
int idx = 1, fw[N], n, sleft;

void update(int idx){
    for (; idx <= n; idx += (idx & -idx)) fw[idx]++;
}

int query(int idx){
    int rs = 0;
    for (; idx; idx -= (idx & -idx)) rs += fw[idx];
    return rs;
}

int main(){
    ifstream cin ("order.in");
    ofstream cout ("order.out");
    cin >> n;
    for (int i=1; i<=n; i++){
        sleft = i;
        int free = n - idx - (query(n) - query(idx));
        if (sleft > free) sleft -= free, idx = 0, sleft %= (n-i+1);
        if (!sleft) sleft = n-i+1;
        //cout << "\n" << idx << " " << sleft << "\n";
        int nxt = idx;
        for (int bit = (1<<15); bit; bit >>= 1){
            if (nxt + bit <= n && nxt + bit - idx - (query(nxt+bit) - query(idx)) < sleft) nxt += bit;
        }
        idx = nxt + 1;
        cout << idx << " ";
        update(idx);
    }
    return 0;
}