Submission #1304562

#TimeUsernameProblemLanguageResultExecution timeMemory
1304562muhammad-ahmadType Printer (IOI08_printer)C++20
60 / 100
1104 ms327680 KiB
#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, bool ch = 1, int dpth = 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]){
			if (ch && ('a' + i) == longest[dpth]){
				left = i;
				continue;
			}
			ans.push_back('a' + i);
			dfs(trie[u][i], 0, dpth + 1);
			ans.push_back('-');
		}
	}
	if (left == -1) return;
	ans.push_back('a' + left);
	dfs(trie[u][left], 1, dpth + 1);
	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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...