Submission #1256635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256635		wedonttalkanymore	Type Printer (IOI08_printer)	C++20	0 / 100	44 ms	49600 KiB

printer

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

const ll N = 1e6 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;

int n;
int child[N][26];
string a[N];
int cnt = 0;
int isend[N];
vector <char> act;

bool cmp(string a, string b) {
	return a.size() < b.size();
}
void add(string &s) {
	int u = 0;
	for (int i = 0; i < s.size(); i++) {
		int k = s[i] - 'a';
		if (!child[u][k]) child[u][k] = ++cnt;
		u = child[u][k];
	}
	isend[u]++;
}

int query(string &s) {
	int u = 0;
	for (int i = 0; i < s.size(); i++) {
		int k = s[i] - 'a';
		if (!child[u][k]) return 0;
		u = child[u][k];
	}
	return isend[u];
}

void dfs(int u, int now, bool ok) {
	if (isend[u]) {
		for (int i = 1; i <= isend[u]; i++) {
			act.push_back('P');
		}
	}
	if (now >= a[n].size()) return;
	if (!ok) {
		for (int k = 0; k < 26; k++) {
			if (child[u][k]) {
				act.push_back('a' + k);
				dfs(child[u][k], now + 1, 0);
				act.push_back('-');
			}
		}
	}
	else {
		for (int k = 0; k < 26; k++) {
			if (child[u][k] && k != a[n][now] - 'a') {
				act.push_back('a' + k);
				dfs(child[u][k], now + 1, 0);
				act.push_back('-');
			}
		}
		int k = a[n][now] - 'a';
		int v = child[u][k];
		act.push_back(a[n][now]);
		dfs(v, now + 1, 1);
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		add(a[i]);
	}
	sort(a + 1, a + n + 1, cmp);
	dfs(0, 0, 1);
	cout << act.size() << '\n';
	for (auto i : act) {
		cout << i;
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 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