Cod sursa(job #3223930)

Utilizator MAlex2019Melintioi George Alexandru MAlex2019 Data 14 aprilie 2024 10:16:28
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

const int maxn = 1e5;
int v[maxn + 1];

int bs(long long x, int n) {
    int st = 1, dr = n + 1;
    while (st < dr) {
        int mij = (st + dr)/2;
        long long res = (long long)mij*(mij - 1)/2;
        if (res == x)
            return mij;
        if (res < x)
            st = mij + 1;
        else
            dr = mij;
    }
    return st;
}

int main() {
    int n;
    long long k;
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        v[i] = i;
    long long right = bs(k, n);
    long long inv = right*(right-1)/2;
    for (int i = 1; i <= n - right; i++)
        v[i] = i;
    if (inv == k) {
        int val = n;
        for (int i = n - right + 1; i <= n; i++)
            v[i] = val--;
    }
    else {
        int skip = inv - k;
        v[n - right + 1] = n - skip;
        int val = n;
        for (int i = n - right + 2; i <= n; i++) {
            if (val == n - skip)
                val--;
            v[i] = val--;
        }
    }
    for (int i = 1; i <= n; i++)
        fout << v[i] << ' ';

    return 0;
}