Cod sursa(job #2033835)

Utilizator FrequeAlex Iordachescu Freque Data 7 octombrie 2017 11:06:34
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 100000 + 5;

int n, ans;
long long k, rest;
int AIB[NMAX];

int zeros(int x)
{
    return x ^ (x & (x - 1));
}

void init()
{
    for (int i = 1; i <= n; ++i)
        AIB[i] = zeros(i);
}

int query(int poz)
{
    int ans = 0;
    for (int i = poz; i; i -= zeros(i))
        ans += AIB[i];
    return ans;
}

void update(int poz, int val)
{
    for (int i = poz; i <= n; i += zeros(i))
        AIB[i] += val;
}

int bin_search(int x)
{
    int st = 1, dr = n, mijl, ans = n;

    while (st <= dr)
    {
        mijl = (st + dr) / 2;
        if (query(mijl) >= x)
        {
            dr = mijl - 1;
            ans = mijl;
        }
        else
            st = mijl + 1;
    }

    return ans;
}

void read()
{
    fin >> n >> k;
}

void write(int x)
{
    fout << x << " ";
}

int main()
{
    read();
    init();

    for (int i = 1; i <= n; ++i)
    {
        rest = 1LL * (n - i) * (n - i - 1) / 2;
        if (rest > k)
        {
            ans = bin_search(1);
            write(ans);
            update(ans, -1);
        }
        else
        {
            ans = bin_search(k - rest + 1);
            write(ans);
            update(ans, -1);
            k = rest;
        }
    }

    return 0;
}