Pagini recente » Cod sursa (job #1124843) | Cod sursa (job #866608) | Diferente pentru problema/density intre reviziile 15 si 12 | Diferente pentru problema/arbquery intre reviziile 10 si 9 | Cod sursa (job #3357159)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
// Folosim un vector global sau alocat dinamic pentru a evita depasirea stivei
int solutie[100005];
bool folosit[100005];
int main() {
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
long long n, k;
if (!(fin >> n >> k)) return 0;
long long stanga = 1;
long long p = 1; // Pozitia curenta in solutie
// Pasul 1: Punem cele mai mici elemente posibile la inceput
while (p <= n) {
long long ramase = n - p;
long long max_inv_ramase = (ramase * (ramase - 1)) / 2;
if (max_inv_ramase >= k) {
solutie[p] = stanga;
folosit[stanga] = true;
stanga++;
p++;
} else {
// Am ajuns la punctul critic
break;
}
}
// Pasul 2: Daca inca mai avem de completat si k > 0
if (p <= n) {
long long ramase = n - p;
long long max_inv_ramase = (ramase * (ramase - 1)) / 2;
// Elementul de pe pozitia curenta trebuie sa lase in urma exact max_inv_ramase
long long de_pus = stanga + (k - max_inv_ramase);
solutie[p] = de_pus;
folosit[de_pus] = true;
p++;
// Pasul 3: Restul elementelor ramase se pun in ordine descrescatoare
// pentru a genera numarul maxim de inversiuni (max_inv_ramase)
for (long long i = n; i >= 1; --i) {
if (!folosit[i]) {
solutie[p] = i;
p++;
}
}
}
// Afisarea rezultatului
for (int i = 1; i <= n; ++i) {
fout << solutie[i] << (i == n ? "" : " ");
}
fout << "\n";
fin.close();
fout.close();
return 0;
}