oj.uz

답안 #122399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122399 2019-06-28T07:04:16 Z turbat Type Printer (IOI08_printer) C++14
10 / 100
 210 ms 84120 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++;
}

inline 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 += "-";
		}
	}
}

inline 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() << '\n';
		for (auto a : ans) cout << a<< '\n';
	}
	else{ 
		cout << ans1.size() << endl;
		for (auto a : ans1) cout << a<< '\n';
	}
}

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 384 KB Output is correct
2 Incorrect 7 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 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 36788 KB Output is correct
2 Correct 210 ms 84120 KB Output is correct
3 Incorrect 107 ms 43700 KB Output isn't correct

Subtask #10
0 / 10.0

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