Submission #238312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238312	2020-06-10T18:43:02 Z	tfg	Devil's Share (RMI19_devil)	C++17	27 / 100	679 ms	262144 KB

devil

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
#include <algorithm>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

std::vector<int> solve(std::vector<int> a) {
	if(a[0] == a.back()) return a;
	//for(auto x : a) std::cout << x << ' ';
	//std::cout << std::endl;
	int sz = 0;
	int mx = a.back();
	while(a.back() == mx) {
		sz++;
		a.pop_back();
	}
	std::vector<std::vector<int>> b(sz, std::vector<int>(1, mx));
	std::vector<int> wtf(sz, 0), inv(1, 0);
	int pt = 0, c = 1;
	std::reverse(a.begin(), a.end());
	while(!a.empty()) {
		for(int l = pt, r = pt; l < sz; l = r) {
			if(a.empty()) {
				break;
			}
			int got = a.back();
			while(r < sz && !a.empty() && a.back() == got) {
				b[r++].push_back(got);
				a.pop_back();
			}
			if(r != sz) {
				for(int i = l; i < r; i++) {
					wtf[i] = c;
				}
				c++;
				inv.push_back(l);
				pt = r;
			}
		}
	}
	for(int i = pt; i < sz; i++) {
		wtf[i] = c;
	}
	c++;
	inv.push_back(pt);
	auto ha = solve(wtf);
	std::vector<int> ans;
	for(auto id : ha) {
		for(auto x : b[inv[id]]) {
			ans.push_back(x);
		}
	}
	//for(auto x : ans) std::cout << x << ' ';
	//std::cout << std::endl;
	return ans;
}

void solve() {
	int k;
	std::vector<int> a;
	std::cin >> k;
	for(int i = 1; i <= 9; i++) {
		int x;
		std::cin >> x;
		while(x--) {
			a.push_back(i);
		}
	}
	std::string end;
	for(int i = 1; i < k; i++) {
		end += char('0' + a.back());
		a.pop_back();
	}
	a = solve(a);
	for(auto x : a) std::cout << x;
	std::reverse(end.begin(), end.end());
	std::cout << end << '\n';
}

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int t;
	std::cin >> t;
	while(t--) {
		solve();
	}
}

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	384 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	2040 KB	Output is correct
2	Correct	199 ms	2040 KB	Output is correct
3	Correct	171 ms	1912 KB	Output is correct
4	Correct	201 ms	2424 KB	Output is correct
5	Correct	152 ms	4132 KB	Output is correct
6	Correct	104 ms	1612 KB	Output is correct
7	Correct	83 ms	1528 KB	Output is correct
8	Correct	83 ms	1640 KB	Output is correct
9	Correct	87 ms	4132 KB	Output is correct

Subtask #3

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	1912 KB	Output is correct
2	Correct	137 ms	1820 KB	Output is correct
3	Correct	57 ms	7568 KB	Output is correct
4	Correct	373 ms	165768 KB	Output is correct
5	Runtime error	679 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4

0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	384 KB	Output is correct
2	Correct	190 ms	2040 KB	Output is correct
3	Correct	199 ms	2040 KB	Output is correct
4	Correct	171 ms	1912 KB	Output is correct
5	Correct	201 ms	2424 KB	Output is correct
6	Correct	152 ms	4132 KB	Output is correct
7	Correct	104 ms	1612 KB	Output is correct
8	Correct	83 ms	1528 KB	Output is correct
9	Correct	83 ms	1640 KB	Output is correct
10	Correct	87 ms	4132 KB	Output is correct
11	Correct	135 ms	1912 KB	Output is correct
12	Correct	137 ms	1820 KB	Output is correct
13	Correct	57 ms	7568 KB	Output is correct
14	Correct	373 ms	165768 KB	Output is correct
15	Runtime error	679 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)