Cod sursa(job #2749087)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 4 mai 2021 22:17:26
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb

#include <iostream>
#include<fstream>
# define N 100005
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

///pt a obtine ordine minima lexicografica, incercam sa tinem fixe de la inceput cat mai multe elem
///si sa le punem in oridne descrescatoare pe cele de la final

long long  n, k;

int main()
{
    int i;
    fin >> n >> k;
    if(k == n * (n-1)/2)///nr max inversiuni---in ordine descresc--suma lui gauss
        for(i = n; i >= 1; --i)
            fout << i << " ";
    if(k == 0)///nicio inversiune
         for(i = 1; i <= n; ++i)
            fout << i << " ";

    long long x = 1;///vedem cate elem trb inversate la sf
    while(x*(x-1)/2 < k)
        x++;

    ///stim sigur ca primele n-x au ramas neschimbate
    for(i = 1; i <= n - x; ++i)
            fout << i << " ";

    ///trb sa verifcam daca am obtinut fix k inversiuni
    if(x*(x-1)/2 == k) ///le afisez in ordine descrescatoare
        for(i = n; i > n - x; --i)
            fout << i << " ";
    else    ///trb sa schimb cv ---> caut elem care ar echilibra inversiunile
        {
            long long dif = x*(x-1)/2 - k;
            ///afisam n-dif mai intai pentru a nu mai provoca dif inversiuni
            fout << n - dif << " ";
            for(i = n; i > n - x; --i)
                if(i != n - dif)
                    fout << i << " ";

        }
    return 0;

}