oj.uz

Submission #219455

# Submission time Handle Problem Language Result Execution time Memory
219455 2020-04-05T10:58:11 Z Sorting Type Printer (IOI08_printer) C++14
100 / 100
 141 ms 55020 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 25000 + 1;
const int kLen = 20 + 1;

struct Trie{
	struct Node{
		map<char, int> next;
		int cnt_end;
		bool last_word;

		Node(){
			cnt_end = 0;
			last_word = false;
		}
	};
	Node nodes[kN * kLen];
	int sz;

	Trie(){
		sz = 1;
	}

	void add_word(const string &word){
		int curr_node = 0;
		for(char c: word){
			if(!nodes[curr_node].next.count(c)){
				nodes[curr_node].next[c] = sz;
				curr_node = sz++;
				continue;
			}

			curr_node = nodes[curr_node].next[c];
		}

		nodes[curr_node].cnt_end++;
	}
};

string s[kN];
Trie trie;
vector<char> operations;

void dfs(int u){
	for(int _ = 0; _ < trie.nodes[u].cnt_end; ++_)
		operations.push_back('P');

	char last_word_char;
	int last_word_idx = -1;
	for(auto t: trie.nodes[u].next){
		if(trie.nodes[t.second].last_word){
			last_word_idx = t.second;
			last_word_char = t.first;
			continue;
		}

		operations.push_back(t.first);
		dfs(t.second);
		operations.push_back('-');
	}

	if(last_word_idx != -1){
		operations.push_back(last_word_char);
		dfs(last_word_idx);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	int max_len = 0;
	for(int i = 0; i < n; ++i){
		cin >> s[i];
		trie.add_word(s[i]);
		max_len = max((int)s[i].size(), max_len);
	}

	for(int i = 0; i < n; ++i){
		if(s[i].size() == max_len){
			int curr_node = 0;
			for(int j = 0; j < s[i].size(); ++j){
				curr_node = trie.nodes[curr_node].next[s[i][j]];
				trie.nodes[curr_node].last_word = true;
			}
			break;
		}
	}

	dfs(0);

	cout << operations.size() << "\n";
	for(char operation: operations)
		cout << operation << "\n";
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s[i].size() == max_len){
      ~~~~~~~~~~~~^~~~~~~~~~
printer.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < s[i].size(); ++j){
                   ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29824 KB Output is correct
2 Correct 22 ms 29824 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29952 KB Output is correct
2 Correct 22 ms 29824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29824 KB Output is correct
2 Correct 22 ms 29824 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29824 KB Output is correct
2 Correct 22 ms 29824 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29952 KB Output is correct
2 Correct 25 ms 30072 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30336 KB Output is correct
2 Correct 25 ms 30584 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31360 KB Output is correct
2 Correct 38 ms 33056 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 33524 KB Output is correct
2 Correct 30 ms 30976 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 39024 KB Output is correct
2 Correct 126 ms 50928 KB Output is correct
3 Correct 82 ms 41456 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 36852 KB Output is correct
2 Correct 141 ms 55020 KB Output is correct
3 Correct 92 ms 43120 KB Output is correct
4 Correct 128 ms 53608 KB Output is correct