Submission #1313308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313308		algoproclub	Type Printer (IOI08_printer)	C++20	100 / 100	108 ms	69132 KiB

printer

// UUID: b08b650b-805d-4583-9783-7cdb77eced46
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> let;
string ans;
int op=0;
string lst;
void insert(string s){
	int pos=0;
	for(int i=0;i<s.size();i++){
		char c=s[i];
		if(!let[pos][c-'a']){
			let[pos][c-'a']=let.size();
			let.push_back(vector<int>(27));
		}
		pos=let[pos][c-'a'];
		if(i==s.size()-1) let[pos][26]=1;
	}
}

void dfs(int pos, int ind){
	if(let[pos][26]){
		op++;
		ans.push_back('P');
	}
	for(int i=0;i<26;i++){
		if (ind<lst.size()&&i != lst[ind] - 'a')
		if(let[pos][i]){
			op++;
			ans.push_back(i+'a');
			dfs(let[pos][i], ind+1);
			op++;
			ans.push_back('-');
		}
	}
	if(ind<lst.size()&&let[pos][lst[ind]-'a']){
		op++;
		ans.push_back(lst[ind]);
		dfs(let[pos][lst[ind]-'a'], ind+1);
		op++;
		ans.push_back('-');
	}
}

int main() {
	int n;
	cin>>n;
	let.resize(1, vector<int>(27));
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		if(s.size()>=lst.size()) lst=s;
		insert(s);
	}
	dfs(0, 0);
	while(ans.back()=='-'){
		ans.pop_back();
		op--;
	}
	cout<<op<<'\n';
	for(int i=0;i<op;i++){
		cout<<ans[i]<<'\n';
	}
}

• 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