Cod sursa(job #3315162)

Utilizator Lex._.Lex Guiman Lex._. Data 12 octombrie 2025 17:38:24
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

ifstream in("farfurii.in");
ofstream out("farfurii.out");

int v[NMAX];

int main()
{
    ///practic trebuie sa gasim sirul minim lexicografic care are k inversiuni
    ///solutie O(n^2)
    int n, k;
    in >> n >> k;
    v[1]=1;
    for(int i=2; i<=n; i++) ///punem farfuria cu numarul i
    {
        int nr_poz=0;
        for(int j=i; j>=1; j--) ///incercam sa o punem pe cea mai din dreapta pozitie posibila
        {
            v[j+1]=v[j];
            if((n-i+1)*(n-i)/2 + (n-i+1)*nr_poz>=k) ///daca putem pune farfuriile cu indicii i, i+1, ..., n intre pozitiile j si j+1
            {
                v[j]=i;
                k-=nr_poz; ///scadem inversiunile deja existente in sirul de pana acum
                break;
            }
            nr_poz++;
        }
    }
    for(int i=1; i<=n; i++)
    {
        out << v[i] << " ";
    }

    return 0;
}