Cod sursa(job #3133811)

Utilizator stefanmo03Mocanu Stefan stefanmo03 Data 26 mai 2023 23:43:16
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
//#include <iostream>
#include <fstream>

using namespace std;
std::ifstream cin("farfurii.in");
std::ofstream cout("farfurii.out");
/*cerinta problemei este echivalenta cu:
Sa se afiseze cea mai mica permutare lexicografic cu n inversiuni.
Se stie ca o permutare desccrescatoare(n, n-1, ... 3, 2, 1) n*(n-1)/2 inversiuni, cele mai multe pt o permutare cu n elemente
Astfel daca numarul de tacamuri k este de forma x*(x-1)/2, cu x nr. natural, atunci permutarea ceruta va arata astfel:
1 2 ... n-x n n-1 .. n-x+1
Daca K>x*(x-1)/2 atunci construim
1 2 ... n-x-1 n n-1 .. n-x+1 n-x care are x*(x-1)/2 inversiuni
Mutam elementul  n-((x+1)*n/2-k) inaintea lui n, scazand in acest fel numarul de inversiuni la k.*/
long long gauss(long long val){
    return (val * (val-1))>>1;
}
int main() {

    long long n,k, val = 0,aux = 0;
    cin>>n>>k;
    while(gauss(val)<k)val++;

    for(long long i=1; i <= n-val;i++)cout<<i<<" ";
    long long x = gauss(val);
    if(x>k) {
        aux = n - (x - k);
        cout<<aux<<" ";
    }

    for(long long i=n;i> n-val;i--)
        if(i!=aux)cout<<i<<" ";
    return 0;
}