Submission #488576

#	Time	Username	Problem	Language	Result	Execution time	Memory
488576		Alex_tz307	Devil's Share (RMI19_devil)	C++17	100 / 100	367 ms	4808 KiB

devil

#include <bits/stdc++.h>

using namespace std;

void TestCase() {
  int k;
  cin >> k;
  vector<int> f(10);
  for (int i = 1; i < 10; ++i) {
    cin >> f[i];
  }
  string last = "";
  for (int i = 9; i > 0 && (int)last.size() < k - 1; --i) {
    int use = min(f[i], k - 1 - (int)last.size());
    f[i] -= use;
    for (int j = 0; j < use; ++j) {
      last += '0' + i;
    }
  }
  reverse(last.begin(), last.end());
  deque<string> dq, q;
  for (int i = 9; i > 0; --i) {
    if (f[i]) {
      for (int j = 0; j < f[i]; ++j) {
        dq.emplace_back(string(1, '0' + i));
      }
      f[i] = 0;
      break;
    }
  }
  for (int i = 1; i < 10; ++i) {
    for (int j = 0; j < f[i]; ++j) {
      q.emplace_back(string(1, '0' + i));
    }
  }
  while (!q.empty()) {
    auto s = q.front();
    q.pop_front();
    dq.back() += s;
    if (dq.back() != dq.front()) {
      q.emplace_back(dq.back());
      dq.pop_back();
    }
    while (!q.empty() && q.back() == dq.front()) {
      dq.emplace_back(q.back());
      q.pop_back();
    }
  }
  for (auto it : dq) {
    cout << it;
  }
  cout << last << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tests;
  cin >> tests;
  for (int tc = 1; tc <= tests; ++tc) {
    TestCase();
  }
  return 0;
}

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