Submission #718216

#	Time	Username	Problem	Language	Result	Execution time	Memory
718216		APROHACK	Type Printer (IOI08_printer)	C++14	100 / 100	152 ms	76092 KiB

printer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
vector<string>vec;
int trie[25*25000][29];//27 for 'P', 28 for size
int cur = 1;
vector<char>ans;
void insert(int node, string &s, int pos){
	if(pos == s.size()){
		trie[node][28] = 1;
		return ;
	}
	//cout << "estamos en node = " << node << "calculando " <<s[pos] << endl; 
	int nxt = (s[pos] >= 'a' ? s[pos]-'a' : 27);
	if(trie[node][nxt] == -1){
		trie[node][nxt] = cur++;
	}	
	insert(trie[node][nxt], s, pos+1);
	trie[node][28] = max(trie[node][28], trie[trie[node][nxt]][28]+1);
}

void recorrer(int node, bool esP){
	int mx = -1, cual = -1;
	for(int i = 0 ; i <= 27 ; i++){
		if(trie[node][i] != -1){
			if(trie[trie[node][i]][28] > mx){
				mx = trie[trie[node][i]][28];
				cual = i;
			}
		}
	}
	for(int i = 0 ; i <= 27 ; i++){
		if(trie[node][i] != -1 and i != cual){
			ans.pb( (i < 27 ? 'a' + i : 'P'));
			recorrer(trie[node][i], i == 27);
		}
	}
	if(cual != -1){
		ans.pb( (cual < 27 ? 'a' + cual : 'P'));
		recorrer(trie[node][cual], cual == 27);
	}
	if(!esP)ans.pb('-');
}



int main(){
	//freopen("input.txt", "r", stdin);
	int n;
	memset(trie, -1, sizeof trie);
	cin>>n;
	string s;
	for(int i = 0 ; i < n ; i ++){
		cin>>s;
		vec.pb(s);
		s+="P";
		insert(0, s, 0);
	}
	recorrer(0, true);
	while(ans.back() == '-')ans.pop_back();
	cout << ans.size() << "\n";
	for(auto i : ans){
		cout << i << "\n";
	}
	
	
}

Compilation message (stderr)

printer.cpp: In function 'void insert(int, std::string&, int)':
printer.cpp:12:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  if(pos == s.size()){
      |     ~~~~^~~~~~~~~~~

• 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