Cod sursa(job #2567034)

Utilizator memecoinMeme Coin memecoin Data 3 martie 2020 14:37:26
Problema Farfurii Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "farfurii";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

#define MAXN 100005

int n, k;
int sol[MAXN];

int main() {
    
    fin >> n >> k;
    
    int j = n;
    
    while ((j - 1) * (j - 2) / 2 > k) {
        j--;
    }
    
    for (int i = 1; i <= (n - j); ++i) {
        sol[i] = i;
    }
    
    int ndx = (n - j) + 1;
    
    set<int> s;
    for (int i = (n - j) + 1; i <= n; ++i) {
        s.insert(i);
    }
    
    for (int i = j; i >= 1; --i) {
        int enoughForLast = (i - 2) * (i - 1) / 2;
        int choose = (k - enoughForLast);
        
        auto it = s.begin();
        advance(it, choose);
        
        sol[ndx] = *it;
        s.erase(sol[ndx]);
        
        k = enoughForLast;
        ndx++;
    }
    
    for (int i = 1; i <= n; ++i) {
        fout << sol[i] << " ";
    }
    
    return 0;
}