Cod sursa(job #2847699)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 11 februarie 2022 11:52:19
Problema Farfurii Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

#define ll long long
using namespace std;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int N;
ll K;

int main() {
    fast();
    ifstream fin("farfurii.in");
    fin >> N >> K;
    int st = 0, dr = N;
    int lastE = 0;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (mid * (mid - 1) / 2 >= K) {
            lastE = mid;
            dr = mid - 1;
        } else st = mid + 1;
    }
    int addAfter = N - lastE;
    K = (long long) lastE * (long long) (lastE - 1LL) / 2 - K;
    int crt = 1;
    ll lastToMove = -1;
    while (K) {
        if (lastE - crt <= K) {
            K -= lastE - crt;
            crt++;
        } else {
            lastToMove = crt + K;
            break;
        }
    }
    ofstream fout("farfurii.out");
    for (int i = 1; i <= N - lastE; i++)
        fout << i << ' ';
    for (int i = 1; i < crt; i++)
        fout << i + addAfter << ' ';
    if (lastToMove != -1)
        fout << lastToMove + addAfter << ' ';
    for (int i = lastE; i >= 1; i--)
        if (i >= crt && i != lastToMove)
            fout << i + addAfter << ' ';
}