Submission #105190

#	Time	Username	Problem	Language	Result	Execution time	Memory
105190		joseacaz	Type Printer (IOI08_printer)	C++17	100 / 100	200 ms	58604 KiB

printer

#include <iostream>
#include <vector>
#include <queue>
#define MAXN 25005
#define pii pair < int, int >
#define mp make_pair

using namespace std;
typedef long long int lld;

struct trie
{
	int child[26], maxSize = 0;
	bool finish = 0;
};

int N, C = 1, answer;
string word;
trie Trie[MAXN * 20];
vector < char > ans;

void add ( string s )
{
	int node = 0, let = 0;
	for ( int i = 0; i < s.length(); i++ )
	{
		let = s[i] - 'a';

		if ( !Trie[node].child[let] )
			Trie[node].child[let] = C++;
		node = Trie[node].child[let];

		Trie[node].maxSize = max ( Trie[node].maxSize, int(s.length() - i) );
	}
	Trie[node].finish = 1;
}

void solve ( int node )
{
	int nextNode = 0;
	priority_queue < pii > PQ;
	for ( int i = 0; i < 26; i++ )
	{
		nextNode = Trie[node].child[i];
		if ( nextNode )
			PQ.push ( mp ( -Trie[nextNode].maxSize, i ) );
	}

	if ( Trie[node].finish )
		ans.push_back ( 'P' );

	while ( !PQ.empty() )
	{
		ans.push_back( char(PQ.top().second + 'a') );
		solve ( Trie[node].child[PQ.top().second] );
		ans.push_back ( '-' );
		PQ.pop();
	}
}

int main ()
{
	cin >> N;
	for ( int i = 0; i < N; i++ )
		cin >> word, add ( word );
	
	solve ( 0 );

	answer = ans.size();

	for ( int i = answer - 1; i >= 0; i-- )
	{
		if ( ans[i] != '-')
			break;
		answer = i;
	}

	cout << answer << "\n";
	for ( int i = 0; i < answer; i++ )
		cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::__cxx11::string)':
printer.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < s.length(); i++ )
                   ~~^~~~~~~~~~~~

• 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