Submission #383794

#	Time	Username	Problem	Language	Result	Execution time	Memory
383794		penguinhacker	Type Printer (IOI08_printer)	C++14	100 / 100	126 ms	48676 KiB

printer

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

#define ll long long
#define ar array

int n, m, c[500001][26];
bool l[500001];
string ans, b;

void dfs(int u = 0) {
	if (l[u])
		ans.push_back('P');
	for (int i = 0; i < 26; ++i)
		if (c[u][i]) {
			ans.push_back('a' + i);
			dfs(c[u][i]);
			ans.push_back('-');
		}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	m = 1;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		if (s.size() > b.size())
			b = s;
		int u = 0;
		for (char d : s) {
			if (!c[u][d - 'a'])
				c[u][d - 'a'] = m++;
			u = c[u][d - 'a'];
		}
		l[u] = 1;
	}
	int u = 0;
	for (char d : b) {
		for (int i = 0; i < 26; ++i)
			if (c[u][i] && i != d - 'a') {
				ans.push_back('a' + i);
				dfs(c[u][i]);
				ans.push_back('-');
			}
		ans.push_back(d);
		u = c[u][d - 'a'];
		if (l[u])
			ans += 'P';
	}
	cout << ans.size() << "\n";
	for (char d : ans)
		cout << d << "\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