oj.uz

Submission #122393

# Submission time Handle Problem Language Result Execution time Memory
122393 2019-06-28T06:55:51 Z turbat Type Printer (IOI08_printer) C++14
10 / 100
 1000 ms 84640 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 6008 KB Output is correct
2 Incorrect 181 ms 12792 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 36824 KB Output is correct
2 Execution timed out 1073 ms 84640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 28984 KB Output isn't correct
2 Halted 0 ms 0 KB -