제출 #238323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238323		tfg	Devil's Share (RMI19_devil)	C++17	100 / 100	194 ms	21292 KiB

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 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44