Submission #299579

#	Time	Username	Problem	Language	Result	Execution time	Memory
299579		AMO5	Type Printer (IOI08_printer)	C++17	100 / 100	212 ms	58576 KiB

printer

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define eb emplace_back
#define ii pair<int,int>

struct tr{
	bool prt=0;
	int len=0;
	int nxt[26];
	tr(){
		prt=0;
		fill(begin(nxt),end(nxt),-1);
	}
};

vector<tr>trie;

void insert(string s){
	int n=s.length();
	int k=0;
	for(int i=0; i<n; i++){
		int j = s[i]-'a';
		if(trie[k].nxt[j]==-1){
			trie[k].nxt[j]=sz(trie);
			trie.emplace_back();
		}
		trie[k].len=max(trie[k].len,n);
		k=trie[k].nxt[j];
	}
	trie[k].len=max(trie[k].len,n);
	trie[k].prt=1;
	return;
}

vector<char>ans;

void dfs(int u=0){
	if(trie[u].prt)ans.eb('P');
	vector<ii>vv;
	for(int i=0; i<26; i++){
		if(trie[u].nxt[i]!=-1){
			vv.eb(trie[trie[u].nxt[i]].len,i);
		}
	}
	sort(vv.begin(),vv.end());
	for(ii x:vv){
		ans.eb(char('a'+x.second));
		dfs(trie[u].nxt[x.second]);
	}
	ans.eb('-');
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	trie.eb();
	int n;
	cin>>n;
	string s;
	for(int i=0; i<n; i++){
		cin>>s;
		insert(s);
	}
	dfs();
	while(ans.back()=='-'){
		ans.pop_back();
	}
	cout<<sz(ans)<<"\n";
	for(char c:ans)cout<<c<<"\n";
	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: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10