Cod sursa(job #3286361)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 14 martie 2025 09:00:18
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
int n, k, i, j, nr, rasp[100002];

static inline int Cb(int k) {
    int st = 1, dr = n;
    int poz = 0;
    while(st <= dr) {
        int mij = st + (dr - st) / 2;
        if(mij * (mij - 1) / 2 <= k) {
            poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return poz;
}

int main() {
    fin >> n >> k;

    nr = Cb(k);
    k -= nr * (nr - 1) / 2;

    for(i = 1         ; i <= n - nr; i++) rasp[i] = i;
	for(i = n - nr + 1; i <= n     ; i++) rasp[i] = n - j++;
	if(k > 0) {
		rasp[n - nr] = rasp[n - k + 1];
		for(i = n - k + 1; i <= n - 1; i++) rasp[i] = rasp[i + 1];
		rasp[n] = n - nr;
	}
	for(i = 1; i <= n; i++) fout << rasp[i] << " ";

    return 0;
}