Submission #1304526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304526		muhammad-ahmad	Type Printer (IOI08_printer)	C++20	60 / 100	1102 ms	327680 KiB

printer

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

// #define int long long

const int N = 3e4;
int v = 0, trie[N * 20][26], C[N];
vector<char> ans;
string longest, cur;

void add(string s){
	int cur = 0, n = s.size();
	for (int i = 0; i < n; i++){
		if (!trie[cur][s[i] - 'a']) {
			trie[cur][s[i] - 'a'] = ++v;
		}
		cur = trie[cur][s[i] - 'a'];
	}
	C[cur]++;
}

void dfs(int u = 0){
	while(C[u] > 0){
		ans.push_back('P');
		C[u]--;
	}
	int left = -1;
	for (int i = 0; i < 26; i++){
		if (trie[u][i]){
			cur += ('a' + i);
			if (cur == longest.substr(0, cur.size())){
				left = i;
				cur.pop_back();
				continue;	
			}
			ans.push_back('a' + i);
			dfs(trie[u][i]);
			ans.push_back('-');
			cur.pop_back();
		}
	}
	if (left == -1) return;
	ans.push_back('a' + left);
	cur += ('a' + left);
	dfs(trie[u][left]);
	cur.pop_back();
	ans.push_back('-');
}

signed main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		string s; cin >> s;
		add(s);
		if (s.size() > longest.size()) longest = s;
	}
	
	int cur = 0;
	
	dfs();
	while (ans.size() && ans.back() == '-') ans.pop_back();
	
	cout << ans.size() << endl;
	for (auto i : ans) cout << i << endl;
	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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10