Cod sursa(job #3301906)

Utilizator AswVwsACamburu Luca AswVwsA Data 1 iulie 2025 02:05:16
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
//O(n) vector de vizitare
//incepi prin a incerca toate pozitiile
//valabile
//e clar ca daca alegi ceva care are sub el alte
//valori, atunci vor aparea inversiuni
//verifici (nr. de chestii care-s sub tine) +
//(n - i) (n - i - 1) / 2 >= k, deoarece vrei doar
//sa vezi cat poti pune cel putin ca sa inca le poti
//face
//daca o faci brut, iei 70p
//ca sa faci 100p, poti optimiza cautarea acelui element
//cu un aib, aint sau poti sa realizezi ca poti forma exact
//suma alegand elementul care-ti face k - (n - i) (n - i - 1) /2
//inversiuni, iar dupa sunt doar elemente puse in ordine
//descrescatoare :)
#include <fstream>
#include <vector>
#include <cassert>
#define ll long long
using namespace std;

const int NMAX = 1e5;

bool seen[NMAX + 1];

ll gauss(int val)
{
    return 1LL * val * (val - 1) / 2;
}

int n;

int main()
{
    ifstream cin("farfurii.in");
    ofstream cout("farfurii.out");
    int i;
    ll k;
    cin >> n >> k;
    i = 1;
    while (i <= n and gauss(n - i) >= k)
    {
        cout << i << " ";
        seen[i] = 1;
        i++;
    }
    int cate = k - gauss(n - i);
    for (i = 1; i <= n and cate > 0; i++)
        cate -= (!seen[i]);
    while (i <= n and seen[i])
        i++;
    cout << i << " ";
    seen[i] = 1;
    for (i = n; i >= 1; i--)
        if (!seen[i])
            cout << i << " ";
}