oj.uz

Submission #897674

# Submission time Handle Problem Language Result Execution time Memory
897674 2024-01-03T14:29:12 Z penguin133 Type Printer (IOI08_printer) C++17
100 / 100
 335 ms 137840 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

map <string, int > mp;

struct node{
	node *nx[26];
	node(){
		for(int i = 0; i < 26; i++)nx[i] = nullptr;
	}
	void upd(string &s, int pos = -1){
		if(pos == (int)s.length() - 1)return;
		if(nx[s[pos + 1] - 'a'] == nullptr)nx[s[pos + 1] - 'a'] = new node();
		nx[s[pos + 1] - 'a']->upd(s, pos + 1);
	}
}*root = new node();

vector <char> x;
string longest;

void dfs(node *cur, string s, int pos){
	if(pos != -1)s += (pos + 'a'), x.push_back(pos + 'a');
	while(mp[s]){
		x.push_back('P');
		mp[s]--;
	}
	int bruv = (int)s.length();
	int f = 1;
	for(int i=0;i<(int)s.length();i++)if(s[i] != longest[i])f = 0;
	for(int i = 0; i< 26; i++){
		if(cur->nx[i] != nullptr && (!f || longest[bruv] != (i + 'a'))){
			dfs(cur->nx[i], s, i);
		}
	}
	for(int i = 0; i < 26; i++){
		if(f && longest[bruv] == (i + 'a'))dfs(cur->nx[i], s, i);
	}
	if(pos != -1)x.push_back('-');
}

void solve(){
	int n; cin >> n;
	for(int i=1;i<=n;i++){
		string s; cin >> s;
		mp[s]++;
		if(longest.length() < s.length())longest = s;
		root->upd(s);
	}
	dfs(root, "", -1);
	while(x.back() == '-')x.pop_back();
	cout << (int)x.size() << '\n';
	for(auto i : x)cout << i << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

printer.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2396 KB Output is correct
2 Correct 6 ms 2904 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8024 KB Output is correct
2 Correct 39 ms 16724 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 19576 KB Output is correct
2 Correct 16 ms 4444 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 49768 KB Output is correct
2 Correct 271 ms 115648 KB Output is correct
3 Correct 144 ms 59240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 38380 KB Output is correct
2 Correct 335 ms 137840 KB Output is correct
3 Correct 167 ms 67276 KB Output is correct
4 Correct 290 ms 129476 KB Output is correct