oj.uz

Submission #1020067

# Submission time Handle Problem Language Result Execution time Memory
1020067 2024-07-11T13:27:00 Z Tob Type Printer (IOI08_printer) C++14
100 / 100
 40 ms 7692 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 25007;

int n, p;
string s[N], s2[N];

bool cmp(int x, int y) {
	int i = 0;
	for (i = 0; i < min((int)s2[x].size(), (int)s2[y].size()); i++) if (s2[x][i] != s2[y][i]) break;
	if (i != s2[x].size() && i != s2[y].size()) return (s2[x][i] < s2[y][i]);
	if (s2[x].size() == s2[y].size()) return (x < y);
	return (s2[x].size() < s2[y].size());
}

int main () {
	FIO;
	cin >> n;
	int mx = 0;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		if (s[i].size() > mx) {
			mx = s[i].size();
			p = i;
		}
		s2[i] = s[i];
	}
	vector <int> v;
	for (int i = 0; i < n; i++) if (i != p) {
		v.pb(i);
		for (int j = 0; j < mx && j < s[i].size() && s[i][j] == s[p][j]; j++) s2[i][j] = 'z'+1;
	}
	sort(all(v), cmp);
	v.pb(p);
	int le = 0;
	string res;
	for (int i = 0; i < n-1; i++) {
		int x = v[i], y = v[i+1];
		while (le < s[x].size()) res += s[x][le++];
		res += 'P';
		int j;
		for (j = 0; j < le && j < s[y].size() && s[x][j] == s[y][j]; j++);
		while (le > j) {res += '-'; le--;}
	}
	while (le < s[p].size()) res += s[p][le++];
	res += 'P';
	
	cout << res.size() << "\n";
	for (auto x : res) cout << x << "\n";

	return 0;
}

Compilation message

printer.cpp: In function 'bool cmp(int, int)':
printer.cpp:22:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if (i != s2[x].size() && i != s2[y].size()) return (s2[x][i] < s2[y][i]);
      |      ~~^~~~~~~~~~~~~~~
printer.cpp:22:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if (i != s2[x].size() && i != s2[y].size()) return (s2[x][i] < s2[y][i]);
      |                           ~~^~~~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:33:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |   if (s[i].size() > mx) {
      |       ~~~~~~~~~~~~^~~~
printer.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int j = 0; j < mx && j < s[i].size() && s[i][j] == s[p][j]; j++) s2[i][j] = 'z'+1;
      |                             ~~^~~~~~~~~~~~~
printer.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   while (le < s[x].size()) res += s[x][le++];
      |          ~~~^~~~~~~~~~~~~
printer.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (j = 0; j < le && j < s[y].size() && s[x][j] == s[y][j]; j++);
      |                         ~~^~~~~~~~~~~~~
printer.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  while (le < s[p].size()) res += s[p][le++];
      |         ~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2596 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3832 KB Output is correct
2 Correct 34 ms 6776 KB Output is correct
3 Correct 25 ms 5920 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3428 KB Output is correct
2 Correct 40 ms 7692 KB Output is correct
3 Correct 27 ms 6388 KB Output is correct
4 Correct 39 ms 7440 KB Output is correct