oj.uz

Submission #963194

# Submission time Handle Problem Language Result Execution time Memory
963194 2024-04-14T17:11:21 Z fzyzzz_z Type Printer (IOI08_printer) C++17
50 / 100
 399 ms 62024 KB 
#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

map<string, int> id; 
int s = 1; 
vector<int> adj[20 * 25000]; 
int bad[20 * 25000]; 
char ch[20 * 25000]; 


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; 
	cin >> n; 
	vector<string> a(n);
	string mx = ""; 
	for (auto & x: a) {
		cin >> x; 
		if (x.size() > mx.size()) mx = x; 
	}

	for (int i = 0; i < 20 * 25000; ++i) bad[i] = 0; 

	for (auto x: a) {
		int at = 0; 
		string cur = ""; 
		for (auto c: x) {
			cur += c; 
			if (id.find(cur) == id.end()) {
				adj[at].push_back(s); 
				id[cur] = s++; 
			}
			at = id[cur]; 
			ch[at] = c; 
			if (x == mx) bad[at] = 1; 
		}
		bad[at] |= 2; 
	}

	string ans = ""; 

	function<void(int)> dfs = [&] (int x) -> void {
		if (x > 0) ans += ch[x]; 
		if (bad[x] & 2) ans += 'P';

		for (auto u: adj[x]) {
			if (!(bad[u] & 1)) {
				dfs(u); 
			}
		}
		for (auto u: adj[x]) {
			if ((bad[u] & 1)) {
				dfs(u); 
			}
		}
		ans += '-'; 
	};
	dfs(0); 

	while (ans.back() == '-') ans.pop_back(); 

	cout << ans.size() << '\n';
	for (auto x: ans) {
		cout << x << '\n';
	}

	return 0; 
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14268 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Incorrect 3 ms 14428 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 7 ms 14740 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 15192 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 17500 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 21992 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 34160 KB Output is correct
2 Correct 399 ms 62024 KB Output is correct
3 Correct 249 ms 39404 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 29308 KB didn't print every word
2 Halted 0 ms 0 KB -