Cod sursa(job #3223797)

Utilizator MAlex2019Melintioi George Alexandru MAlex2019 Data 13 aprilie 2024 17:36:07
Problema Farfurii Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 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);
    stack<int> linie;
    vector<int> rares;
    for (int i = 1; i <= n; i++) {
        if (n - i == right && right <= k) {
            linie.push(i);
            k -= right;
            right--;
            if (right > k)
                right = k;
            continue;
        }
        rares.push_back(i);
    }
    while (!linie.empty()) {
        rares.push_back(linie.top());
        linie.pop();
    }
    for (auto elem: rares)
        fout << elem << ' ';

    return 0;
}