oj.uz

Submission #934444

# Submission time Handle Problem Language Result Execution time Memory
934444 2024-02-27T10:28:38 Z bashNewbie Type Printer (IOI08_printer) C++17
100 / 100
 71 ms 48456 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)

const int N = 5e5+7, K = 26;
int adj[N][K+1], len, ret;
string ms;

inline void pr(char c) {
	cout << c << "\n";
}
inline void pr(int c) {
	cout << char(c+'a') << "\n";
}

void add(string& s) {
	int x = 0;
	for(char ch: s) {
		int c = ch-'a', y = adj[x][c];
		if(!y) adj[x][c] = ++len, ret++;
		x = adj[x][c];
	}
	adj[x][K] = 1;
}

void dfs(int x, int in, int d) {
	int c = in && d < (int)ms.size()? ms[d]-'a': -1;

	for(int j = 0; j < K+1; j++) {
		int y = adj[x][j];
		if(!y) continue;

		if(j == K) pr('P'); else {
			if(!in || in && j != c) pr(j), dfs(y, 0, d+1);
		}
	}

	if(~c) pr(c), dfs(adj[x][c], 1, d+1);
	if(!in) pr('-');
}

int main() {
	fast_io;

	ret = 0;

	int n, l = 0; string s;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> s, add(s);
		if((int)s.size() > l) l = (int)s.size(), ms = s;
	}
	ret <<= 1, ret += n-l;

	cout << ret << "\n";
	dfs(0, 1, 0);
}

Compilation message

printer.cpp: In function 'void dfs(int, int, int)':
printer.cpp:38:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |    if(!in || in && j != c) pr(j), dfs(y, 0, d+1);
      |              ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 9 ms 6232 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9048 KB Output is correct
2 Correct 4 ms 1880 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19548 KB Output is correct
2 Correct 66 ms 40784 KB Output is correct
3 Correct 31 ms 20968 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13916 KB Output is correct
2 Correct 71 ms 48456 KB Output is correct
3 Correct 40 ms 23704 KB Output is correct
4 Correct 61 ms 45648 KB Output is correct