Cod sursa(job #2303508)

Utilizator Constantin.Dragancea Constantin Constantin. Data 16 decembrie 2018 14:01:38
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010;
ll n, k, dp[N], a[N];
bool u[N];
int main(){
    ifstream cin ("farfurii.in");
    ofstream cout ("farfurii.out");
    cin >> n >> k;
    for (int i=1; i<=n; i++) dp[i] = 1LL*(i-1)*i/2;
    int dr = n;
    while (k > 0){
        int ans = 0;
        for (int i=(1<<20); i; i >>= 1)
            if (i + ans < dr && dp[ans + i] < k) ans += i;
        a[dr] = n - ans; k -= ans; dr--; u[n-ans] = 1;
    }
    for (int i=1, dr = 0; i<=n; i++)
        if (!u[i]) a[++dr] = i;
    for (int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}