Submission #863100

#	Time	Username	Problem	Language	Result	Execution time	Memory
863100		mgl_diamond	Type Printer (IOI08_printer)	C++17	0 / 100	31 ms	29892 KiB

printer

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define fi first
#define se second
#define ins push_back
#define vec vector
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(i, v) for(auto &i : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()

struct node {
	int child[26], en = 0, dep = 0;
	node() { memset(child, -1, sizeof(child)); }
};

vec<node> trie;
string ret;

void add(int i, int u, const string &s) {
	if (i == sz(s)) {
		trie[u].en += 1;
		return;
	}
	int ch = s[i]-'a';

	if (trie[u].child[ch] == -1) {
		trie[u].child[ch] = sz(trie);
		trie.ins(node());
	}

	add(i+1, trie[u].child[ch], s);
	trie[u].dep = max(trie[u].dep, trie[trie[u].child[ch]].dep + 1);
}

void dfs(int u) {
	for(int i=0; i<trie[u].en; ++i) ret.ins('P');
	
	vec<int> order;
	for(int i=0; i<26; ++i) if (trie[u].child[i] != -1) 
		order.ins(i);
	
	sort(all(order), [&](int i, int j){
		return trie[trie[u].child[i]].dep < trie[trie[u].child[j]].dep;
	});

	for(int i : order) {
		ret.ins(i + 'a');
		dfs(trie[u].child[i]);
		ret.ins('-');
	}
}

void solve() {
	trie.ins(node());
	int n;
	cin >> n;
	foru(i, 1, n) {
		string s;
		cin >> s;
		add(0, 0, s);
	}
	dfs(0);
	while (!ret.empty() && ret.back() == '-') ret.pop_back();
	cout << ret.size() << "\n" << ret;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 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