Submission #1232808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232808		lanaskarica	Type Printer (IOI08_printer)	C++20	20 / 100	65 ms	37816 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define pii pair <int, int>
#define fi first
#define se second

const int MAXN = 1e6 + 5;

int cnt, d[MAXN];
bool ispisi[MAXN];
char slovo[MAXN];
string s;

vector <int> v[MAXN];
vector <char> rj;

void dodaj(int a, int idx) {
	int x = -1;
	for (auto e : v[a]) {
		if (slovo[e] == s[idx]) x = e; 
	}
	if (x == -1) {
		v[a].push_back(cnt);
		slovo[cnt] = s[idx];
		x = cnt; cnt++;
	}
	
	if (idx + 1 >= s.size()) {ispisi[x] = 1; return;}
	d[idx + 1] = d[idx] + 1;
	dodaj(x, idx + 1);
}

void dfs(int a) {
	if (ispisi[a] == 1) rj.push_back('P');
	int mx = 0, x = -1;
	for (auto e : v[a]) {
		if (d[e] > mx) {mx = d[e]; x = e;}
	}
	for (auto e : v[a]) {
		if (e == x) continue;
		rj.push_back(slovo[e]);
		dfs(e);
		rj.push_back('-');
	}
	if (x != -1) {
		rj.push_back(slovo[x]);
		dfs(x);
		rj.push_back('-');
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	cnt = 1;
	for (int i = 0; i < n; i++) {
		cin >> s; dodaj(0, 0);
	}
	
	dfs(0);
	
	int i = rj.size() - 1;
	while (rj[i] == '-') {rj.pop_back(); i--;} 
	
	cout << rj.size() << "\n";
	for (auto e : rj) cout << e << "\n";
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10