oj.uz

답안 #122398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122398 2019-06-28T07:03:19 Z turbat Type Printer (IOI08_printer) C++14
10 / 100
 1000 ms 84136 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 (){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	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:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < ans.size();i++){
                 ~~^~~~~~~~~~~~
printer.cpp:79: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 324 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 1908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 6060 KB Output is correct
2 Incorrect 159 ms 12664 KB Output isn't correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 195 ms 14872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 528 ms 36800 KB Output is correct
2 Execution timed out 1078 ms 84136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 407 ms 28984 KB Output isn't correct
2 Halted 0 ms 0 KB -