제출 #1195103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195103		damamila	Type Printer (IOI08_printer)	C++20	80 / 100	1095 ms	20964 KiB

printer

#include <bits/stdc++.h>

using namespace std;

vector<set<tuple<int, int, int>>> g (2); //l, letter, index
bool fin [200000];
int cnt = 2;
string ans;

void insrt(string s, int i, int idx) {
	if (s.size() == i) {
		fin[idx] = 1;
		return;
	}
	int next = s[i]-'a';
	int idx2 = 0;
	int len2 = s.size();
	int other = 0;
	for (auto [len, let, ind] : g[idx]) {
		if (let == next) {
			len2 = max(len2, len);
			other = len;
			idx2 = ind;
			break;
		}
	}
	if (idx2 == 0) {
		idx2 = cnt;
		cnt++;
		g.push_back({});
		g[idx].insert({len2, next, idx2});
	} else {
		g[idx].erase({other, next, idx2});
		g[idx].insert({len2, next, idx2});
	}
	insrt(s, i+1, idx2);
}

void dfs(int u) {
	if (fin[u]) ans = ans+'P'+'\n';
	for (auto [len, let, v] : g[u]) {
		ans = ans+char('a'+let)+'\n';
		dfs(v);
		ans = ans+'-'+'\n';
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		insrt(s, 0, 1);
	}
	dfs(1);
	while (ans[ans.size()-1] == '-' || ans[ans.size()-1] == '\n') ans.pop_back();
	ans = ans + '\n';
	cout << ans.size()/2 << '\n' << ans;
}

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