Submission #584606

#	Time	Username	Problem	Language	Result	Execution time	Memory
584606		Drew_	Type Printer (IOI08_printer)	C++17	100 / 100	152 ms	57452 KiB

printer

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);

int n;
static int ctr = 0;

inline void out(char c)
{
	if (ctr < n)
		cout << c << '\n';
	ctr += c == 'P';
}

struct Trie
{
	bool is_word = false, lst = false;
	// Trie* to[26] = {};
	map<char, Trie*> to;

	Trie() {}
};

int main()
{
	fastio;

	cin >> n;

	string best = "";
	cin >> best;

	int sum = 0;
	Trie* root = new Trie();
	for (int i = 1; i < n; ++i)
	{
		string s; cin >> s;
		if (s.size() > best.size())
			swap(s, best);

		Trie* cur = root;
		for (char &c : s)
		{
			if (!(cur -> to.count(c)))
				sum++, cur -> to[c] = new Trie();
			cur = cur -> to[c];
		}
		cur -> is_word = true;
	}

	Trie* cur = root;
	for (char &c : best)
	{
		if (!(cur -> to.count(c)))
			sum++, cur -> to[c] = new Trie();
		cur = cur -> to[c];
		cur -> lst = true;
	}
	cur -> is_word = true;

	const auto dfs = [&](const auto &self, Trie* node) -> void
	{
		if (node -> is_word)
		{
			out('P');
			node -> is_word = false;
		}

		char pend = 0;
		for (const auto &[x, y] : node -> to)
		{
			if (y -> lst)
			{
				pend = x;
				continue;
			}
			out(x);
			self(self, y);
		}

		if (pend)
		{
			out(pend);
			self(self, node -> to[pend]);
		}

		out('-');
	};

	cout << 2 * sum + n - (int)best.size() << '\n';
	dfs(dfs, root);

	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