Submission #699129

#	Time	Username	Problem	Language	Result	Execution time	Memory
699129		Doncho_Bonboncho	Type Printer (IOI08_printer)	C++14	100 / 100	125 ms	70836 KiB

printer

#include <bits/stdc++.h>
#include <iterator>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

struct trie{
	int go[26];
	bool word;
	bool big[26];

	trie( ){
		for( int i=0 ; i<26 ; i++ ){
			go[i] = -1;
			big[i] = false;
		}
		word = false;
	}
};	

std::vector<trie> tree;
int size = 1;

void add( const std::string& word, int currNode, int indWord  ){

	if( indWord == word.size() ){
		tree[currNode].word = true;
		return;
	}
	int currW = word[indWord] - 'a';
	if( tree[currNode].go[currW] == -1 ){
		tree[currNode].go[currW] = size;
		tree.push_back(trie());
		size++;
	}
	add( word, tree[currNode].go[currW], indWord +1 );
}


void addBig( const std::string& word, int currNode, int indWord  ){
	if( word.size() == indWord ){
		tree[currNode].word = true;
		return;
	}
	int currW = word[indWord] - 'a';
	if( tree[currNode].go[currW] == -1 ){
		tree[currNode].go[currW] = size;
		tree.push_back(trie());
		size++;
	}

	tree[currNode].big[currW] = true;

	addBig( word, tree[currNode].go[currW], indWord +1 );
}

std::vector<char> nas;
void traverse( int currNode ){
	if( tree[currNode].word  ) nas.push_back('P');

	for( int i=0 ; i<26 ; i++ ){
		if( tree[currNode].go[i] != -1 and !tree[currNode].big[i] ){
			nas.push_back(('a' + i));
			traverse( tree[currNode].go[i] );
			nas.push_back('-');
		}
	}	
	for( int i=0 ; i<26 ; i++ ){
		if( tree[currNode].go[i] != -1 and tree[currNode].big[i] ){
			nas.push_back(('a' + i));
			traverse( tree[currNode].go[i] );
			nas.push_back('-');
		}
	}

}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n;
	std::cin>>n;
	
	tree.push_back( trie() );

	std::vector<std::pair<int, std::string>> inp;
	inp.resize(n);
	for( int i=0 ; i<n ; i++ ){
		std::cin>>inp[i].second;
		inp[i].first = inp[i].second.size();
	}

	std::sort( inp.begin(), inp.end() );

	for( int i=0 ; i<n ; i++ ){
	//	add( inp[i].second, 0, 0 );
		if( i != n-1 ) add( inp[i].second, 0, 0 );
		else addBig( inp[i].second, 0, 0 );
	}

	traverse( 0 );

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

	std::cout<<nas.size()<<"\n";
	for( auto j : nas ) std::cout<<j<<"\n";

	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(const string&, int, int)':
printer.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  if( indWord == word.size() ){
      |      ~~~~~~~~^~~~~~~~~~~~~~
printer.cpp: In function 'void addBig(const string&, int, int)':
printer.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |  if( word.size() == indWord ){
      |      ~~~~~~~~~~~~^~~~~~~~~~

• 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