제출 #442036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442036		huukhang	Type Printer (IOI08_printer)	C++11	100 / 100	123 ms	51188 KiB

printer

/*
						   Khangnh's code

“You can either experience the pain of discipline or the pain of regret. 
						The choice is yours.”
*/

// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")

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

#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout);

#define ll long long
// #define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
typedef pair<int, int> pii;

const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;

struct node {
	int child[26];
	int fin, vis;
};

string mx;
vector<char> ans;
struct trie {
	int n;
	node t[500005];

	trie() : n(0) {
		memset(t[0].child, -1, sizeof(t[0].child));
		t[0].fin = t[0].vis = 0;
	}

	void init(int u) {
		memset(t[u].child, -1, sizeof(t[u].child));
		t[u].fin = t[u].vis = 0;
	}

	void push(string &s) {
		int p = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (t[p].child[s[i] - 'a'] == -1) {
				init(++n);
				t[p].child[s[i] - 'a'] = n;
			}
			p = t[p].child[s[i] - 'a'];
		}
		++t[p].fin;
	}

	void dfs(int u, int dep, bool longest) {
		if (t[u].fin > 0) ans.pb('P');

		int c = mx[dep] - 'a';
		for (int i = 0; i < 26; ++i) {
			if (i == c && longest) continue;
			if (t[u].child[i] != -1) {
				ans.pb(char(i + 'a'));
				dfs(t[u].child[i], dep + 1, 0);
				ans.pb('-');
			}
		}

		if (dep < mx.size() && longest) {
			ans.pb(char(c + 'a'));
			if (t[u].child[c] != -1) dfs(t[u].child[c], dep + 1, 1);
		}
	}
} t;

int n;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		string s;
		cin >> s;

		t.push(s);
		if (mx.size() < s.size()) mx = s;
	}

	t.dfs(0, 0, 1);

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

signed main() {
	#ifdef LOCAL
		fileopen("input", "output");
		auto start = clock();
	#endif
	#ifndef LOCAL
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test = 1;
//	cin >> test;
	for (int tc = 1; tc <= test; ++tc) solve();
	#ifdef LOCAL
		auto end = clock();
		cout << "\n\nExecution time : " << double(end - start)/CLOCKS_PER_SEC << "[s]";
	#endif
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

printer.cpp: In member function 'void trie::push(std::string&)':
printer.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
printer.cpp: In member function 'void trie::dfs(int, int, bool)':
printer.cpp:79:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if (dep < mx.size() && longest) {
      |       ~~~~^~~~~~~~~~~

• 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: 10 / 10
• Subtask 10: 10 / 10