oj.uz

Submission #53781

# Submission time Handle Problem Language Result Execution time Memory
53781 2018-07-01T07:25:49 Z 0^0(#1430) Type Printer (IOI08_printer) C++11
100 / 100
 92 ms 5396 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
string str[25005];
int len[26];
void solve(int le, int ri,int idx) {
	if (le > ri)return;
	memset(len, 0, sizeof(len));
	for (int i = le; i <= ri; i++) {
		if (str[i].size() == idx) {
			le++;
			continue;
		}
		len[str[i][idx] - 'a'] = max(len[str[i][idx] - 'a'], (int)str[i].size());
	}
	sort(str + le, str + ri + 1, [&](const string &a, const string &b) {
		if (a[idx] == b[idx])return a.size() < b.size();
		if (len[a[idx] - 'a'] == len[b[idx] - 'a'])return a[idx] < b[idx];
		return len[a[idx] - 'a'] < len[b[idx] - 'a'];
	});
	int pre = le;
	for (int i = le; i < ri; i++) {
		if (str[i][idx] != str[i + 1][idx]) {
			solve(pre, i, idx + 1);
			pre = i + 1;
		}
	}
	solve(pre, ri, idx + 1);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> str[i];
	solve(0, n - 1, 0);
	vector<char> ans;
	string st = "";
	for (int i = 0; i < n; i++) {
		int idx = 0;
		while (idx < st.size() && st[idx] == str[i][idx])idx++;
		while (idx < st.size()) {
			st.pop_back();
			ans.push_back('-');
		}
		for (int j = idx; j < str[i].size(); j++) {
			ans.push_back(str[i][j]);
			st.push_back(str[i][j]);
		}
		ans.push_back('P');
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << '\n';
	return 0;
}

Compilation message

printer.cpp: In function 'void solve(int, int, int)':
printer.cpp:10:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (str[i].size() == idx) {
       ~~~~~~~~~~~~~~^~~~~~
printer.cpp: In function 'int main()':
printer.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (idx < st.size() && st[idx] == str[i][idx])idx++;
          ~~~~^~~~~~~~~~~
printer.cpp:42:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (idx < st.size()) {
          ~~~~^~~~~~~~~~~
printer.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = idx; j < str[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~
printer.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1332 KB Output is correct
2 Correct 3 ms 1364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1388 KB Output is correct
2 Correct 6 ms 1532 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1676 KB Output is correct
2 Correct 15 ms 1948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1948 KB Output is correct
2 Correct 13 ms 1948 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2704 KB Output is correct
2 Correct 89 ms 4748 KB Output is correct
3 Correct 65 ms 4748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4748 KB Output is correct
2 Correct 92 ms 5396 KB Output is correct
3 Correct 68 ms 5396 KB Output is correct
4 Correct 79 ms 5396 KB Output is correct