Submission #122393

#	Time	Username	Problem	Language	Result	Execution time	Memory
122393		turbat	Type Printer (IOI08_printer)	C++14	10 / 100	1073 ms	84640 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define N 25005

int n, level[25];

struct trie{
	trie *c[26];
	int cnt = 0;	
};

string ans, ans1;

void insert(trie *cur, string& s){
	for (char a : s){
		if (!cur->c[a - 'a']) cur->c[a - 'a'] = new trie();
		cur = cur->c[a - 'a'];
	}
	cur->cnt++;
}

void print(trie *cur){
	for (int i = 1; i <= cur->cnt; i++)
		ans += "P";
	for (int i = 0;i < 26;i++){
		if (cur->c[i]) {
			ans += char(i + 'a');
			print(cur->c[i]);
			ans += "-";
		}
	}
}

void print1(int lvl, trie *cur){
	for (int i = 1; i <= cur->cnt; i++)
		ans1 += "P";
	for (int i = level[lvl];i < 26;i++){
		if (cur->c[i]) {
			ans1 += char(i + 'a');
			print1(lvl + 1, cur->c[i]);
			ans1 += "-";
		}
	}
	for (int i = 0;i < level[lvl];i++){
		if (cur->c[i]) {
			ans1 += char(i + 'a');
			print1(lvl + 1, cur->c[i]);
			ans1 += "-";
		}
	}
}

int main (){
	cin >> n;
	trie *root = new trie();
	while (n--){
		string st;
		cin >> st;
		insert(root, st);
	}
	print(root);
	string mx, nw;
	int cnt = 0, mxcnt = 0;
	for (int i = 0;i < ans.size();i++){
		if (ans[i] == 'P') {
			if (cnt > mxcnt){
				mxcnt = cnt;
				mx = nw;
			}
			cnt = 0;
			continue;
		}
		if (ans[i] == '-') nw.pop_back(),cnt++;
		else nw += ans[i];
	}
	for (int i = 0;i < mx.size();i++)
		level[i] = mx[i] - 'a';
	print1(0, root);
	while (ans.back() == '-') ans.pop_back();
	while (ans1.back() == '-') ans1.pop_back();
	if (ans.size() < ans1.size()) {
		cout << ans.size() << endl;
		for (auto a : ans) cout << a<< endl;
	}
	else{ 
		cout << ans1.size() << endl;
		for (auto a : ans1) cout << a<< endl;
	}
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < ans.size();i++){
                 ~~^~~~~~~~~~~~
printer.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < mx.size();i++)
                 ~~^~~~~~~~~~~

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