Submission #543932

#	Time	Username	Problem	Language	Result	Execution time	Memory
543932		sliviu	Type Printer (IOI08_printer)	C++17	100 / 100	112 ms	99632 KiB

printer

#include <bits/stdc++.h>

using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	struct node {
		node* s[26] = {};
		char letter;
		int end = 0;
		node() {}
		node(char x) : letter(x) {}
	} *root = new node;
	auto insert = [&](const string& s) {
		node* cur = root;
		for (auto x : s) {
			if (!cur->s[x - 'a'])
				cur->s[x - 'a'] = new node(x);
			cur = cur->s[x - 'a'];
		}
		cur->end = 1;
	};
	vector<char> sol;
	function<void(node*)> dfs = [&](node* nod) {
		if (nod->end)
			sol.emplace_back('P');
		for (int i = 0; i < 26; ++i)
			if (nod->s[i]) {
				sol.emplace_back(nod->s[i]->letter);
				dfs(nod->s[i]);
				sol.emplace_back('-');
			}
	};
	int n;
	string maxs;
	cin >> n;
	while (n--) {
		string s;
		cin >> s;
		insert(s);
		if (s.length() > maxs.length())
			maxs = s;
	}
	node* cur = root;
	for (auto x : maxs) {
		swap(cur->s[25], cur->s[x - 'a']);
		cur = cur->s[25];
	}
	dfs(root);
	while (sol.back() == '-')
		sol.pop_back();
	cout << sol.size() << '\n';
	for (auto x : sol)
		cout << x << '\n';
}

• 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