Submission #897674

#	Time	Username	Problem	Language	Result	Execution time	Memory
897674		penguin133	Type Printer (IOI08_printer)	C++17	100 / 100	335 ms	137840 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

map <string, int > mp;

struct node{
	node *nx[26];
	node(){
		for(int i = 0; i < 26; i++)nx[i] = nullptr;
	}
	void upd(string &s, int pos = -1){
		if(pos == (int)s.length() - 1)return;
		if(nx[s[pos + 1] - 'a'] == nullptr)nx[s[pos + 1] - 'a'] = new node();
		nx[s[pos + 1] - 'a']->upd(s, pos + 1);
	}
}*root = new node();

vector <char> x;
string longest;

void dfs(node *cur, string s, int pos){
	if(pos != -1)s += (pos + 'a'), x.push_back(pos + 'a');
	while(mp[s]){
		x.push_back('P');
		mp[s]--;
	}
	int bruv = (int)s.length();
	int f = 1;
	for(int i=0;i<(int)s.length();i++)if(s[i] != longest[i])f = 0;
	for(int i = 0; i< 26; i++){
		if(cur->nx[i] != nullptr && (!f || longest[bruv] != (i + 'a'))){
			dfs(cur->nx[i], s, i);
		}
	}
	for(int i = 0; i < 26; i++){
		if(f && longest[bruv] == (i + 'a'))dfs(cur->nx[i], s, i);
	}
	if(pos != -1)x.push_back('-');
}

void solve(){
	int n; cin >> n;
	for(int i=1;i<=n;i++){
		string s; cin >> s;
		mp[s]++;
		if(longest.length() < s.length())longest = s;
		root->upd(s);
	}
	dfs(root, "", -1);
	while(x.back() == '-')x.pop_back();
	cout << (int)x.size() << '\n';
	for(auto i : x)cout << i << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

printer.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

• 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