Submission #1304460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304460		muhammad-ahmad	Type Printer (IOI08_printer)	C++20	60 / 100	409 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], 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;
}

• 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