Submission #494360

#	Time	Username	Problem	Language	Result	Execution time	Memory
494360		cadmiumsky	Devil's Share (RMI19_devil)	C++14	100 / 100	1044 ms	5444 KiB

devil

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

deque< pair<string,int> >deq;

int freq[10];

void testcase() {
  int n;
  cin >> n;
  --n;
  string s="",sus;
  for(int i=0; i<9; i++)
    cin >> freq[i];
  for(int i=8; i>=0; i--) {
    while(freq[i] && n) {
      n--;
      s+='1'+i;
      freq[i]--;
    }
  }
  reverse(s.begin(),s.end());
  for(int i=0; i<9; i++) {
    if(freq[i])
      sus='1'+i,deq.push_back(make_pair(sus,freq[i]));
  }
  while(deq.size()>1) {
    //cout << deq.size() <<'\n';
    auto x=deq.back();
    deq.pop_back();
    while(x.second>0) {
      auto temp=deq.front();
      deq.pop_front();
      auto nou=pair<string,int>{x.first+temp.first,min(temp.second,x.second)};
      x.second-=nou.second;
      temp.second-=nou.second;
      deq.push_back(nou);
      if(temp.second)
        deq.push_front(temp);
      //cout << "+ " << nou.first << ' '<< nou.second << '\n';
    }
  }
  auto x=deq.front();
  while(x.second--)
    cout << x.first;
  cout << s <<'\n';
  deq.pop_back();
}

int main() {
  int t;
  cin >> t;
  while(t--)
    testcase();
}

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