Submission #855073

#	Time	Username	Problem	Language	Result	Execution time	Memory
855073		vjudge1	Type Printer (IOI08_printer)	C++14	90 / 100	1006 ms	54980 KiB

printer

// Problem: Type Printer
// Contest: Virtual Judge-OJUZ
// URL: https://vjudge.net/problem/OJUZ-IOI08_printer
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,trie[N][30],tot=1;
bool sum[N],flag[N],last=0;
string s,ll,ans;
void insert(string a){
	int p=1;
	int len=a.size();
	for(int i=0;i<len;i++){
		int ch=a[i]-'a';
		if(!trie[p][ch]) trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	sum[p]=true;
	return;
}
void Mark(string a){
	int p=1;
	int len=a.size();
	for(int i=0;i<len;i++){
		int ch=a[i]-'a';
		p=trie[p][ch];
		flag[p]=true;
	}
	return;
}
void dfs(int now){
	if(sum[now]) ans+='P';
	int x=-1;
	for(int i=0;i<26;i++){
		int t=trie[now][i];
		if(!t) continue;
		if(flag[t]) x=i;
		else{
			ans+=(i+'a');
			dfs(t);
		}
	}
	if(x!=-1){
		ans+=(x+'a');
		dfs(trie[now][x]);
	}
	if(flag[now] && x==-1) last=1;
	if(!last) ans+='-';
	return;
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		insert(s);
		if(ll.size()<s.size()) ll=s;
	}
	Mark(ll);
	dfs(1);
	int len=ans.size();
	cout<<len<<endl;
	for(int i=0;i<len;i++) cout<<ans[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: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10