Submission #1326572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326572		crispxx	Type Printer (IOI08_printer)	C++20	30 / 100	96 ms	85100 KiB

printer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct node {
	char c;
	
	bool flag;
	
	int sz;
	
	node *ch[26];
	
	node(char c = ' ', bool flag = false, int sz = 1) : c(c), flag(flag), sz(sz) {
		for(int i = 0; i < 26; i++) {
			ch[i] = NULL;
		}
	}
};

void add(node *root, const string &s) {
	node *cur = root;
	
	for(auto &c : s) {
		if(cur -> ch[c - 'a'] == NULL) {
			cur -> ch[c - 'a'] = new node(c);
		}
		
		cur = cur -> ch[c - 'a'];
	}
	
	cur -> flag = true;
}

void solve() {
	int n; cin >> n;
	
	vector<string> s(n);
	
	node *root = new node();
	
	for(auto &str : s) {
		cin >> str;
		add(root, str);
	}
	
	{
		auto dfs = [&](auto &&self, node *cur) -> void {
			for(int i = 0; i < 26; i++) {
				if(cur -> ch[i] != NULL) {
					self(self, cur -> ch[i]);
					cur -> sz += cur -> ch[i] -> sz;
				}
			}
		};
		
		dfs(dfs, root);
	}
	
	vector<char> ans;
	
	{
		auto dfs = [&](auto &&self, node *cur) -> void {
			vector<array<int, 2>> b;
			
			for(int i = 0; i < 26; i++) {
				if(cur -> ch[i] != NULL) {
					b.push_back({cur -> ch[i] -> sz, i});
				}
			}
			
			sort(b.begin(), b.end());
			
			if(cur -> c != ' ') ans.push_back(cur -> c);
			
			if(cur -> flag) ans.push_back('P');
			
			for(auto [sz, i] : b) {
				self(self, cur -> ch[i]);
			}
			
			if(cur -> c != ' ') ans.push_back('-');
		};
		
		dfs(dfs, root);
	}
	
	while(!ans.empty() && ans.back() == '-') ans.pop_back();
	
	cout << ans.size() << '\n';
	
	for(auto &c : ans) cout << c << '\n';
}

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10