Submission #1288510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288510		islam_2010	Type Printer (IOI08_printer)	C++20	100 / 100	661 ms	104468 KiB

printer

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define int long long
#define pb push_back
#define se second
#define fi first

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;
const int sz = 5e5+5;
const int inf = 1e9 + 7;

int bin_pow(int x, int b) {
	int res = 1;
	while (b > 0) {
		if (b & 1) {
			res = (res * x) % mod;
		}
		x = (x * x) % mod;
		b >>= 1;
	}
	return res;
 
}


struct modint{
	int x;
	modint(int val): x(val){}
	modint operator*(modint other){
		return 1LL*x*other.x%mod;
	}modint operator-(modint other){
		return (x-other.x)%mod;
	}modint operator+(modint other){
		return (x+other.x)%mod;
	}
};

int trie[sz][27], is_end[sz], path[sz];
string ans = "";
int last = 1;
void add(string s, int x){
	int node = 0;
	for(auto i: s){
		if(trie[node][i-'a'] == 0) {
			trie[node][i-'a']=last++;
		}node = trie[node][i-'a'];
		path[node] = max(path[node], x);
	}is_end[node] = 1;
	
}

void dfs(int node){
	if(is_end[node]){
		ans.pb('P');
	}int ok = -1;
	for(int i = 0; i < 26; i++){
		if(trie[node][i] == 0){
			continue;
		}if(path[trie[node][i]]){
			ok = i;
			continue;
		}ans.pb(i + 'a');
		dfs(trie[node][i]);
	}if(ok != -1){
		ans.pb(ok + 'a');
		dfs(trie[node][ok]);
	}if(!path[node]){
		ans.pb('-');
	}
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("main.in", "r", stdin);
    // freopen("main.out", "w", stdout);
	
	int n;
	cin >> n;
	int mx = 0;
	string c;
	vector<string> s(n);
	for(int i = 0; i < n; i++){
		cin >> s[i];
		if(mx < s[i].size()){
			c = s[i];
			mx = s[i].size();
		}
	}for(int i = 0; i < n; i++){
		if(s[i] != c){
			add(s[i], 0);
		}
	}add(c, 1);
	dfs(0);
	cout << ans.size()-1 << endl;
	ans.pop_back();
	for(auto i: ans){
		cout << i << endl;
		
	}
	
}

• 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