Submission #920474

#	Time	Username	Problem	Language	Result	Execution time	Memory
920474		BBart888	Type Printer (IOI08_printer)	C++14	20 / 100	37 ms	48476 KiB

printer

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <random>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}



using namespace std;
const int MAXN = 1e6 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
typedef complex<ll> Point;
const int K = 600;


int n;
int trie[MAXN][27];
string str;
int node_cnt;
bool stop[MAXN];
int longest[MAXN];
vector<char> answer;

void add(const string & str)
{
	int curr_node = 0;
	for (int i = 0; i < str.size(); i++)
	{
		int nxt = str[i] - 'a';
		if (trie[curr_node][nxt] == 0)
			trie[curr_node][nxt] = ++node_cnt;
		curr_node = trie[curr_node][nxt];
	}
	stop[curr_node] = true;
}

vector<pair<int, int>> order[MAXN];

void dfs(int v)
{
	longest[v] = 1;

	for (int i = 0; i < 27; i++)
	{
		int nxt = trie[v][i];
		if (nxt > 0)
		{
			dfs(nxt);
			order[v].push_back({ longest[nxt],i });
			longest[v] = max(longest[v], longest[nxt] + 1);
		}
	}

	sort(order[v].begin(), order[v].end());
}

void print_it(int v)
{
	if (stop[v])
	{
		answer.push_back('P');
		answer.push_back('-');
		return;
	}

	for (int i = 0; i < order[v].size(); i++)
	{
		int nxt_char = order[v][i].second;
		int nxt_node = trie[v][nxt_char];
		answer.push_back((char)(nxt_char + 'a'));
		print_it(nxt_node);
	}
	answer.push_back('-');
}


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

	//fileIO("cardgame");

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> str;
		add(str);
	}

	dfs(0);

	print_it(0);

	while (answer.back() == '-')
		answer.pop_back();

	cout << answer.size() << '\n';

	for (auto x : answer)
		cout << x << '\n';


	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(const string&)':
printer.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < str.size(); i++)
      |                  ~~^~~~~~~~~~~~
printer.cpp: In function 'void print_it(int)':
printer.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i = 0; i < order[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

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