제출 #1304459

#제출 시각아이디문제언어결과실행 시간메모리
1304459muhammad-ahmadType Printer (IOI08_printer)C++20
60 / 100
383 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], ch[N][26];
vector<char> ans;

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;
			ch[cur][s[i] - 'a'] = s[i];
		}
		cur = trie[cur][s[i] - 'a'];
	}
	C[cur]++;
}

void dfs(int u = 0){
	while(C[u] > 0){
		ans.push_back('P');
		C[u]--;
	}
	for (int i = 0; i < 26; i++){
		if (trie[u][i]){
			ans.push_back(ch[u][i]);
			dfs(trie[u][i]);
			ans.push_back('-');
		}
	}
}

signed main(){
	int n; cin >> n;
	string longest;
	for (int i = 1; i <= n; i++){
		string s; cin >> s;
		add(s);
		if (s.size() > longest.size()) longest = s;
	}
	
	int cur = 0;
	for (int i = 0; i < (int) longest.size(); i++){
		int num = longest[i] - 'a';
		if (num != 25){
		swap(trie[cur][num], trie[cur][25]);
		swap(ch[cur][num], ch[cur][25]);}
		cur = trie[cur][25];
	}
	
	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...