Submission #963195

#	Time	Username	Problem	Language	Result	Execution time	Memory
963195		fzyzzz_z	Type Printer (IOI08_printer)	C++17	100 / 100	503 ms	71068 KiB

printer

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

using ll = long long; 

map<string, int> id; 
int s = 1; 
vector<int> adj[20 * 25000]; 
int bad[20 * 25000]; 
char ch[20 * 25000]; 


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; 
	cin >> n; 
	vector<string> a(n);
	string mx = ""; 
	for (auto & x: a) {
		cin >> x; 
		if (x.size() > mx.size()) mx = x; 
	}

	for (int i = 0; i < 20 * 25000; ++i) bad[i] = 0; 

	for (auto x: a) {
		int at = 0; 
		string cur = ""; 
		for (auto c: x) {
			cur += c; 
			if (id.find(cur) == id.end()) {
				adj[at].push_back(s); 
				id[cur] = s++; 
			}
			at = id[cur]; 
			ch[at] = c; 
			if (x == mx) bad[at] |= 1; 
		}
		bad[at] |= 2; 
		// cout << at << '\n';
	}

	string ans = ""; 

	function<void(int)> dfs = [&] (int x) -> void {
		// cout << "nd " << x << '\n';
		if (x > 0) ans += ch[x]; 
		if (bad[x] & 2) ans += 'P';

		for (auto u: adj[x]) {
			if (!(bad[u] & 1)) {
				dfs(u); 
			}
		}
		for (auto u: adj[x]) {
			if ((bad[u] & 1)) {
				dfs(u); 
			}
		}
		ans += '-'; 
	};
	dfs(0); 

	while (ans.back() == '-') ans.pop_back(); 

	cout << ans.size() << '\n';
	for (auto x: ans) {
		cout << x << '\n';
	}

	return 0; 
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10