oj.uz

Submission #122390

# Submission time Handle Problem Language Result Execution time Memory
122390 2019-06-28T06:54:08 Z turbat Type Printer (IOI08_printer) C++14
0 / 100
 590 ms 37168 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();
	cout << ans << endl;
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Expected integer, but "tptttykduyvxjbzhqupP" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Expected integer, but "eejzatjmnqxctnP--------------h...--------nP-xxvebmcP-------yerxP" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Expected integer, but "hjxgqkP------iupqiqP------ppgq...afyveyujP------------xrmqggqbyP" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Expected integer, but "bhvdxrpthaP----------edczvdgoy...-----xcdyqxxmomndP-----------pP" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 484 KB Expected integer, but "abbblauqkfdP----------edP--svh...vkP----rpwfexP------yyauyvyazzP" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1792 KB Expected integer, but "aPaisxlhagqbjwbP-------------b...peilcbtP-------------zasnihjsoP" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 6072 KB Expected integer, but "aPacaoP---izjpfrpvhbP---------...vfpecP----------------lncP---oP" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 15192 KB Expected integer, but "aPadmeP---ejuixzggakP---------...---------xxxP---zzwjpobpgilitkP" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 590 ms 37168 KB Expected integer, but "aPaadfP--iznyxP-----nqjP----bo...wP--------------ygnldzidmxohgdP" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 29068 KB Expected integer, but "aPaPbakyloxqrjP----------chfaP...cvP----------zdbacP----fgmldszP" found
2 Halted 0 ms 0 KB -