Submission #238323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238323	2020-06-10T18:56:32 Z	tfg	Devil's Share (RMI19_devil)	C++17	100 / 100	194 ms	21292 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;
	std::vector<int> wtf(sz, 0), cur(1, mx);
	int pt = 0, c = 0;
	std::reverse(a.begin(), a.end());
	while(!a.empty()) {
		//std::cout << "entering while" << std::endl;
		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) {
				r++;
				a.pop_back();
			}
			if(r != sz) {
				//std::cout << "pushing " << got << " to new" << std::endl;
				for(int i = l; i < r; i++) {
					wtf[i] = c;
				}
				c++;
				b.push_back(cur);
				b.back().push_back(got);
				pt = r;
			} else {
				//std::cout << "pushing " << got << " to cur" << std::endl;
				cur.push_back(got);
			}
		}
	}
	//std::cout << "c is " << c << ", pt is " << pt << std::endl;
	for(int i = pt; i < sz; i++) {
		wtf[i] = c;
	}
	c++;
	b.push_back(cur);
	cur.clear();
	//for(auto x : wtf) std::cout << x << ' ';
	//std::cout << std::endl;
	auto ha = solve(wtf);
	std::vector<int> ans;
	for(auto id : ha) {
		//std::cout << "getting id " << id << std::endl;
		for(auto x : b[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	189 ms	1676 KB	Output is correct
2	Correct	164 ms	1784 KB	Output is correct
3	Correct	143 ms	1784 KB	Output is correct
4	Correct	194 ms	1784 KB	Output is correct
5	Correct	73 ms	1544 KB	Output is correct
6	Correct	67 ms	1400 KB	Output is correct
7	Correct	64 ms	1400 KB	Output is correct
8	Correct	62 ms	1648 KB	Output is correct
9	Correct	62 ms	3196 KB	Output is correct

Subtask #3

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	1656 KB	Output is correct
2	Correct	84 ms	1784 KB	Output is correct
3	Correct	39 ms	2396 KB	Output is correct
4	Correct	70 ms	11332 KB	Output is correct
5	Correct	134 ms	21292 KB	Output is correct

Subtask #4

44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	384 KB	Output is correct
2	Correct	189 ms	1676 KB	Output is correct
3	Correct	164 ms	1784 KB	Output is correct
4	Correct	143 ms	1784 KB	Output is correct
5	Correct	194 ms	1784 KB	Output is correct
6	Correct	73 ms	1544 KB	Output is correct
7	Correct	67 ms	1400 KB	Output is correct
8	Correct	64 ms	1400 KB	Output is correct
9	Correct	62 ms	1648 KB	Output is correct
10	Correct	62 ms	3196 KB	Output is correct
11	Correct	121 ms	1656 KB	Output is correct
12	Correct	84 ms	1784 KB	Output is correct
13	Correct	39 ms	2396 KB	Output is correct
14	Correct	70 ms	11332 KB	Output is correct
15	Correct	134 ms	21292 KB	Output is correct
16	Correct	133 ms	2040 KB	Output is correct
17	Correct	152 ms	2296 KB	Output is correct
18	Correct	126 ms	1912 KB	Output is correct
19	Correct	176 ms	2808 KB	Output is correct
20	Correct	46 ms	1528 KB	Output is correct
21	Correct	45 ms	1400 KB	Output is correct
22	Correct	40 ms	1488 KB	Output is correct
23	Correct	54 ms	2884 KB	Output is correct