Submission #1186819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186819		Ekber_Ekber	Type Printer (IOI08_printer)	C++20	100 / 100	214 ms	90096 KiB

printer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
#define unset unordered_set
#define unmap unordered_map
#define pqueue priority_queue
#define ordered_set_less tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_set_greater tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
 
struct point{
 
};
 
int ctoi(char x) {
	return (int)x - 'a';
}
 
int sumab(int a, int b) {
	return (a + b) * (b - a + 1) / 2;
}
 
int gcd(int a, int b) {
	return (b == 0 ? a : gcd(b, a % b));
}
 
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
 
void print(vector <auto> &v) {
	for (const auto &i : v) cout << i << ' ';
}
 
void print_p(vector <pair<auto, auto>> &v) {
	for (const auto &i : v) cout << i.ff << ' ' << i.ss << endl;
}
 
int compress(int n, vector <int> &v) {
	vector <pair<int, int>> x(n);
	for (int i=0; i < n; i++) {
		x[i] = {v[i], i};
	}
	sort(all(x));
	int nxt=1;
	for (int i=0; i < n-1; i++) {
		if (x[i].ff == x[i+1].ff) {
			x[i].ff = nxt;
		}
		else x[i].ff = nxt++;
	}
	x[x.size()-1].ff = nxt;
	for (int i=0; i < n; i++) {
		swap(x[i].ff, x[i].ss);
	}
	sort(all(x));
	for (int i=0; i < n; i++) {
		v[i] = x[i].ss;
	}
	return nxt;
}
 
int compress_p(int n, vector <pair<int, int>> &v) {
	vector <pair<int, int>> q;
	for (int i=0; i < n; i++) {
		q.pb({v[i].ff, i});
		q.pb({v[i].ss, i});
	}
	sort(all(q));
	int nxt=0;
	for (int i=0; i < 2 * n - 1; i++) {
		if (q[i].ff == q[i+1].ff) q[i].ff = nxt;
		else q[i].ff = nxt++;
	}
	q.back().ff = nxt;
	for (auto &i : q) swap(i.ff, i.ss);
	sort(all(q));
	for (int i=0; i < 2*n; i+=2) {
		v[i/2].ff = q[i].ss;
		v[i/2].ss = q[i+1].ss;
	}
	return nxt;
}
 
void timelimit() {
	int x = 1e+9;
	while (x--) x++;
}
 
void runtime() {
	int x = 1, y = 0;
	cout << x / y;
}
 
constexpr int MAX =450000, INF = 1e+9, MOD = 1e+9 + 7, K = 18;
vector <unordered_map<int, int>> g(MAX+2);
vector <int> cnt(MAX+2, 0);
vector <char> st, is(MAX+2, 0);
set <int> use;
int nxt=1;
int res=0;

bool check(int x) {
	int sz = use.size();
	use.insert(x);
	if (sz == use.size()) return 0;
	return 1;
}

void add(string k) {
	int u = 1;
// 	cout << "a";
	int sz = k.size();
	cnt[u] = max(cnt[u], sz);
	for (int i=0; i < k.size(); i++) {
		int x = ctoi(k[i]);
		if (g[u][x] == 0) {
			if (nxt >= 1e+6) timelimit();
			g[u][x] = ++nxt;
		}
		u = g[u][x];
		cnt[u] = max(cnt[u], sz - i - 1);
	}
	is[u] = 1;
}

void dfs(int u=1) {
	if (is[u]) {
		if (check(u)) st.pb('P');
	}
	res++;
	vector <array <int, 3>> x;
	for (auto &i : g[u]) {
		x.pb({cnt[g[u][i.ff]], g[u][i.ff], i.ff});
	}
	sort(all(x));
	for (auto &i : x) {
		st.pb((char)(i[2] + 'a'));
		dfs(i[1]);
	}
	st.pb('-');
	res++;
}

void _() {
	int n;
	cin >> n;
	int ma=0;
	while (n--) {
		string k;
		cin >> k;
		add(k);
		ma = max(ma, (int)k.size());
	}
	dfs();
	while (st.back() == '-') st.ppb();
	cout << st.size() << endl;
	for (char &i : st) cout << i << endl;
}
 
signed main() {
  // cout << 'a';
 
// 	GOOD_LUCK
 
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	freopen("log.txt", "w", stderr);
 
	int tests=1;
// 	cin >> tests;
	for (int i=1; i <= tests; i++) {
//		cout << "Case #" << i << ": ";
		_();
		// cout << endl;
	}
 
//	int n;
//	while (cin >> n) {
//		_(n);
//		cout << endl;
//	}
 
	return 0;
}
// Problem X
// by Ekber_Ekber
/*
 
*/

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen("log.txt", "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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