Submission #699129

#TimeUsernameProblemLanguageResultExecution timeMemory
699129Doncho_BonbonchoType Printer (IOI08_printer)C++14
100 / 100
125 ms70836 KiB
#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 ){
      |      ~~~~~~~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...