Cod sursa(job #2578061)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 10 martie 2020 14:20:44
Problema Farfurii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

int aib[100005];
int n, f, i;

void update(int poz, int val) {
    while(poz <= n) {
        aib[poz] += val;
        poz += (poz&-poz);
    }
}

int query(int poz) {
    int s = 0;
    while(poz > 0) {
        s += aib[poz];
        poz -= (poz&-poz);
    }
    return s;
}

int cb(int val) {
    int step = 1;
    while(step < n) step <<= 1;

    for(int i = 0; step; step >>= 1)
         if(i + step <= n)
            if(val >= aib[i+step]) {
                i += step;
                val -= aib[i];
                if (!val) {
                    return i;
                }
            }
    return -1;
}

void solve() {
    for(i = 1; i <= n; i++) {
        long long inv = 1LL*(n-i)*(n-i-1)/2;
        if(inv > f)
            fout << i << ' ';
        else
            break;
    }

    for(int k = i; k <= n; k++)
        update(k, 1);

    for(int k = i; k <= n; k++) {
        long long inv = 1LL*(n-k)*(n-k-1)/2;
        int poz = cb(f-inv+1);
        fout << poz << ' ';
        update(poz, -1);
        f = inv;
    }
}

int main() {
    fin >> n >> f;
    solve();
}