Submission #385456

#	Time	Username	Problem	Language	Result	Execution time	Memory
385456		negar_a	Type Printer (IOI08_printer)	C++14	100 / 100	241 ms	78308 KiB

printer

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 25e3 * 20 + 5;
int mat[maxn][26], h[maxn], mh[maxn], x[maxn];
vector <pair <int, char>> adj[maxn];
vector <char> ans;

int cnt = 1;
void add(string s, int v, int h){
	if(h == (int)s.size()){
		x[v] ++;
		return;
	}
	if(!mat[v][s[h] - 'a']){
		mat[v][s[h] - 'a'] = cnt;
		adj[v].pb({cnt, s[h]});
		cnt ++;
	}
	add(s, mat[v][s[h] - 'a'], h + 1);
}

bool cmp(pair <int, char> a, pair <int, char> b){
	return mh[a.F] < mh[b.F];
}

void dfs(int v){
	sort(adj[v].begin(), adj[v].end(), cmp);
	for(int i = 0; i < x[v]; i ++){
		ans.pb('P');
	}
	for(auto p : adj[v]){
		int u = p.F;
		ans.pb(p.S);
		dfs(u); 
	}
	ans.pb('-');
}
void dfs1(int v){
	mh[v] = h[v];
	for(auto p : adj[v]){
		int u = p.F;
		h[u] = h[v] + 1;
		dfs1(u); 
		mh[v] = max(mh[v], mh[u]);
	}
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		string s;
		cin >> s;
		add(s, 0, 0);
	}
	dfs1(0);
	dfs(0);
	while(ans.back() == '-'){
		ans.pop_back();
	}
	cout << ans.size() << '\n';
	for(char u : ans){
		cout << u << '\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