Cod sursa(job #1874635)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 10 februarie 2017 11:43:31
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#define AMAX 300010
#define NMAX 100010

using namespace std;

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

int tree[AMAX], A[NMAX];

void update(int node, int left, int right, int position, int value) {
    if(left == right) {
        tree[node] += value;
        return;
    } else {
        int m = (left+right)>>1;
        if(position <= m) {
            update(2*node, left, m, position, value);
        } else {
            update(2*node+1, m+1, right, position, value);
        }
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

int query(int node, int left, int right, long long position){
    if(left == right){
       return left;
    }
    int m = (left+right)>>1;
    if(tree[2*node] >= position)
        return query(2*node, left, m, position);
    position -= tree[2*node];
    return query(2*node+1, m+1, right, position);
}

int main()
{
    int N;
    long long k;
    fin>>N>>k;
    for(int i = 1; i <= N; ++i) {
        update(1, 1, N, i, 1);
    }
    for(int i = N; i >= 1; --i) {
        if(k <= 1LL*(i-1)*(i-2)/2) {
            int position = query(1, 1, N, 1);
            update(1, 1, N, position, -1);
            fout<<position<<' ';
        } else {
            long long aux = k - 1LL*(i-1)*(i-2)/2;
            k = k - aux;
            int position = query(1, 1, N, aux+1);
            update(1, 1, N, position, -1);
            fout<<position<<' ';
        }
    }
    return 0;
}