Cod sursa(job #2466340)

Utilizator aurelionutAurel Popa aurelionut Data 1 octombrie 2019 21:48:45
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>

using namespace std;

const int NMAX = 100005;
long long n, k;
int ans[NMAX];
bool used[NMAX];

int main()
{
    ifstream fin("farfurii.in");
    ofstream fout("farfurii.out");
    fin >> n >> k;
    int p;
    for (int i = 1;i <= n;++i)
    {
        long long val = 1LL * (n - i) * (n - i + 1) / 2;
        long long nextval = 1LL * (n - i) * (n - i - 1) / 2;
        if (val >= k && nextval < k)
        {
            p = i;
            break;
        }
    }
    for (int i = 1;i < p;++i)
    {
        ans[i] = i;
        used[i] = true;
    }
    int last = p - 1, cnt = 0;
    for (int i = p;i <= n;++i)
    {
        long long aux = 1LL * (n - i) * (n - i - 1) / 2;
        for (int j = last + 1;j <= n;++j)
        {
            if (cnt + aux >= k)
            {
                ans[i] = j;
                last = j;
                used[j] = true;
                k -= cnt;
                break;
            }
            else
                ++cnt;
        }
        if (ans[i] == n)
        {
            ++i;
            int j = n;
            while (i <= n)
            {
                while (used[j] == true)
                    --j;
                used[j] = true;
                ans[i] = j;
                ++i;
            }
            break;
        }
    }
    for (int i = 1;i <= n;++i, fout << " ")
        fout << ans[i];
    fin.close();
    fout.close();
    return 0;
}