Cod sursa(job #2641313)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 10 august 2020 23:04:29
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <vector>
using namespace std;
long long bs(long long k , long long n)
{
    long long st , dr , med , last;
    st = 1;
    dr = n;
    last = -1;
    while(st <= dr)
    {
        med = (st + dr) / 2;
        if(med * (med - 1) / 2 >= k)
        {
            last = med;
            dr = med - 1;
        }
        else
            st = med + 1;
    }
    return last;
}
vector <int> v;
long long bs(long long k)
{
    long long st , dr , med , last;
    st = 0;
    dr = v.size() - 1;
    k = k - (v.size() - 1) * (v.size() - 2) / 2;
    last = -1;
    while(st <= dr)
    {
        med = (st + dr) / 2;
        if(med >= k)
        {
            last = med;
            dr = med - 1;
        }
        else
            st = med + 1;
    }
    return last;
}
int main()
{
    freopen("farfurii.in" , "r" , stdin);
    freopen("farfurii.out" , "w" , stdout);
    long long n , m , x , y , i;
    scanf("%lld%lld" , &n , &m);
    x = bs(m , n);
    n = n - x;
    for(i = 1 ; i <= n ; i ++)
        printf("%lld " , i);
    for(i = 1 ; i <= x ; i ++)
        v.push_back(i);
    for(i = 1 ; i <= x ; i ++)
    {
        y = bs(m);
        m = m - y;
        printf("%lld " , v[y] + n);
        v.erase(v.begin() + y);
    }
    return 0;
}