Cod sursa(job #1327115)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 26 ianuarie 2015 13:20:57
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#define MAXN 100000
#define LOG 17
using namespace std;

long long n;
int aib[MAXN + 1];

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

int query(int p) {
    int answ = 0;
    while (p) {
        answ += aib[p];
        p -= (p & (-p));
    }
    return answ;
}

inline int find(int cnt) {
    int p = 0, step = (1 << LOG);
    while (step) {
        int pos = p + step;
        if (pos <= n && query(pos) < cnt)
            p = pos;
        step >>= 1;
    }

    return p + 1;
}

int main () {
    ifstream cin("farfurii.in");
    ofstream cout("farfurii.out");

    long long k;
    cin >> n >> k;

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

    for (int i = 1 ; i <= n ; ++i) {
       long long maxinv = (long long)((n - i) * (n - i - 1)) / 2;
       long long diff = (long long)k - maxinv;
       if (diff <= 0) {
           int p = find(1);
           cout << p << " ";
           update(p, -1);
       }
       else {
           int p = find(diff + 1);
           cout << p << " ";
           update(p, -1);
           k -= diff;
       }
    }

    return 0;
}