제출 #330837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330837		AlexPop28	Devil's Share (RMI19_devil)	C++11	100 / 100	85 ms	7148 KiB

devil

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

void SolveTest() {
  int k; cin >> k;
  vector<int> freq(10);
  for (int i = 1; i < 10; ++i) {
    cin >> freq[i]; 
  }
  
  string suff;
  int dig = 9;
  for (int i = 0; i < k - 1; ++i) {
    while (freq[dig] == 0) --dig;
    suff += dig + '0';
    --freq[dig];
  }
  reverse(suff.begin(), suff.end());

  while (freq[dig] == 0) --dig;
  pair<string, int> mx = {string(1, dig + '0'), freq[dig]};

  vector<pair<string, int>> q;
  for (int i = 0; i < dig; ++i) {
    if (freq[i] > 0)
      q.emplace_back(string(1, i + '0'), freq[i]); 
  }

  for (int it = 0; it < (int)q.size(); ++it) {
    auto mn = q[it];

    while (mn.second >= mx.second) {
      mx.first += mn.first;
      mn.second -= mx.second;
    }

    if (mn.second > 0) {
      q.emplace_back(mx.first + mn.first, mn.second);
      mx.second -= mn.second;
    }
  }

  for (int i = 0; i < mx.second; ++i)
    cout << mx.first;
  cout << suff << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t; cin >> t;
  while (t--) {
    SolveTest();
  }
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44