Submission #258068

#	Time	Username	Problem	Language	Result	Execution time	Memory
258068		lyc	Devil's Share (RMI19_devil)	C++14	100 / 100	265 ms	15156 KiB

devil

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

int T, K, S, D[10];

string solve(vector<pair<string,int>> add, vector<string> pre) {
	int d = 0, s = 0;
	while (d < SZ(add)) {
		int ps = s, i = s;
		while (d < SZ(add)) {
			//~ TRACE(x.first _ x.second);
			while (add[d].second) {
				pre[i++] += add[d].first;
				--add[d].second;
				if (i == SZ(pre)) i = s;
			}
			++d;
			s = i;
		}
		
		//~ for (auto x : pre) cout << x << '\n';
		//~ cout << endl;
		
		vector<string> pre2;
		FOR(j,ps,s-1) {
			//~ TRACE("ADD" _ j _ pre[j]);
			if (add.back().first == pre[j]) ++add.back().second;
			else add.emplace_back(pre[j],1);
		}
	}
	
	string res = "";
	FOR(i,s,SZ(pre)-1) res += pre[i];
	return res;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> T;
	while (T--) {
		cin >> K;
		S = 0;
		FOR(i,1,9){ cin >> D[i]; S += D[i]; }
		
		string suf = "";
		vector<string> pre;
		RFOR(i,9,1){
			while (D[i]) {
				if (SZ(suf) < K-1) suf += char('0'+i);
				else {
					string s = "";
					s += char('0'+i);
					pre.emplace_back(s);
				}
				--D[i];
			}
			if (!pre.empty()) break;
		}
		reverse(ALL(suf));
		//~ TRACE(suf);
		//~ FOR(i,1,9){ cout << D[i] << ' '; } cout << endl;
		
		vector<pair<string,int>> toAdd;
		FOR(i,1,9) if (D[i]) {
			string s = "";
			s += char('0'+i);
			toAdd.emplace_back(s,D[i]);
		}
		string ans = solve(toAdd,pre) + suf;
		
		cout << ans << '\n';
		
		cout.flush();
	}
}

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