Cod sursa(job #3357159)

Utilizator parus_majorParus Major parus_major Data 6 iunie 2026 18:06:24
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#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;
}