oj.uz

Submission #667340

# Submission time Handle Problem Language Result Execution time Memory
667340 2022-12-01T07:17:13 Z marvinthang Type Printer (IOI08_printer) C++17
100 / 100
 122 ms 99532 KB 
#include <bits/stdc++.h>

using namespace std;

#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          FORE(i, v)  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

struct Node {
	Node *child[26];
	int terminal;
	Node() {
		REP(i, 26) child[i] = nullptr;
		terminal = 0;
	}
};

int N;
string maxS;
Node *root = new Node();

void addString(const string &s) {
	Node *p = root;
	FORE(it, s) {
		if (p->child[*it - 'a'] == nullptr) p->child[*it - 'a'] = new Node();
		p = p->child[*it - 'a'];
	}
	p->terminal++;
}

void init(void) {
	cin >> N;
	int sum = 0;
	REP(i, N) {
		string s; cin >> s;
		sum += s.size();
		if (maxS.size() < s.size()) maxS = s;
		addString(s);
	}
}

string res;

void dfs(Node *p, int depth, bool type) {
	REP(i, p->terminal) res += 'P';
	if (depth == maxS.size()) return;
	if (type) {
		REP(i, 26) if (p->child[i] != nullptr && i != maxS[depth] - 'a') {
			res += char(i + 'a');
			dfs(p->child[i], depth + 1, 0);
			res += '-';
		}
		res += maxS[depth];
		dfs(p->child[maxS[depth] - 'a'], depth + 1, 1);
	} else {
		REP(i, 26) if (p->child[i] != nullptr) {
			res += char(i + 'a');
			dfs(p->child[i], depth + 1, 0);
			res += '-';
		}
	}
}

void process(void) {
	dfs(root, 0, 1);
	cout << res.size() << '\n';
  	for (char c: res) cout << c << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("type-printer");
	init();
	process();
	return (0^0);
}

Compilation message

printer.cpp: In function 'void dfs(Node*, int, bool)':
printer.cpp:46:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  if (depth == maxS.size()) return;
      |      ~~~~~~^~~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:7:67: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:72:2: note: in expansion of macro 'file'
   72 |  file("type-printer");
      |  ^~~~
printer.cpp:7:100: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:72:2: note: in expansion of macro 'file'
   72 |  file("type-printer");
      |  ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5844 KB Output is correct
2 Correct 19 ms 12588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14696 KB Output is correct
2 Correct 7 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36348 KB Output is correct
2 Correct 104 ms 83728 KB Output is correct
3 Correct 55 ms 43128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28520 KB Output is correct
2 Correct 122 ms 99532 KB Output is correct
3 Correct 61 ms 49004 KB Output is correct
4 Correct 102 ms 93952 KB Output is correct