oj.uz

Submission #1106196

# Submission time Handle Problem Language Result Execution time Memory
1106196 2024-10-29T13:56:05 Z Rainmaker2627 Type Printer (IOI08_printer) C++17
100 / 100
 171 ms 99780 KB 
#include<bits/stdc++.h>
using namespace std;

vector<char> sol;

struct trie_node {
	bool end;
	int depth;
	trie_node* child[26];

	trie_node(int d) {
		end=false;
		depth=d;
		for (int i = 0; i < 26; ++i) child[i]=nullptr;
	}

	void add(string s, int i=0) {
		if (i==s.length()) {
			end=true;
		} else {
			if (child[s[i]-'a']==nullptr) child[s[i]-'a']=new trie_node(depth+1);
			child[s[i]-'a']->add(s, i+1);
		}
	}

	void traverse(char avoid) {
		if (end) sol.push_back('P');
		for (char i = 'a'; i <= 'z'; ++i) {
			if (i==avoid || child[i-'a']==nullptr) continue;
			sol.push_back(i);
			child[i-'a']->traverse('-');
			sol.push_back('-');
		}
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int n;
	cin >> n;

	string l="";
	trie_node begin(0);
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		if (s.length()>l.length()) l=s;
		begin.add(s);
	}

	trie_node *cur = &begin;
	for (int i = 0; i < l.length(); ++i) {
		cur->traverse(l[i]);
		cur=cur->child[l[i]-'a'];
		sol.push_back(l[i]);
	} sol.push_back('P');

	cout << sol.size() << '\n';
	for (auto i : sol) {
		cout << i << '\n';
	}

	return 0;
}

Compilation message

printer.cpp: In member function 'void trie_node::add(std::string, int)':
printer.cpp:18:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   if (i==s.length()) {
      |       ~^~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0; i < l.length(); ++i) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1872 KB Output is correct
2 Correct 4 ms 2384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5968 KB Output is correct
2 Correct 20 ms 12624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14804 KB Output is correct
2 Correct 9 ms 3408 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 36548 KB Output is correct
2 Correct 131 ms 83644 KB Output is correct
3 Correct 83 ms 43200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28612 KB Output is correct
2 Correct 171 ms 99780 KB Output is correct
3 Correct 97 ms 49092 KB Output is correct
4 Correct 152 ms 94184 KB Output is correct