oj.uz

Submission #863100

# Submission time Handle Problem Language Result Execution time Memory
863100 2023-10-19T15:23:19 Z mgl_diamond Type Printer (IOI08_printer) C++17
0 / 100
 31 ms 29892 KB 
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define fi first
#define se second
#define ins push_back
#define vec vector
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(i, v) for(auto &i : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()

struct node {
	int child[26], en = 0, dep = 0;
	node() { memset(child, -1, sizeof(child)); }
};

vec<node> trie;
string ret;

void add(int i, int u, const string &s) {
	if (i == sz(s)) {
		trie[u].en += 1;
		return;
	}
	int ch = s[i]-'a';

	if (trie[u].child[ch] == -1) {
		trie[u].child[ch] = sz(trie);
		trie.ins(node());
	}

	add(i+1, trie[u].child[ch], s);
	trie[u].dep = max(trie[u].dep, trie[trie[u].child[ch]].dep + 1);
}

void dfs(int u) {
	for(int i=0; i<trie[u].en; ++i) ret.ins('P');
	
	vec<int> order;
	for(int i=0; i<26; ++i) if (trie[u].child[i] != -1) 
		order.ins(i);
	
	sort(all(order), [&](int i, int j){
		return trie[trie[u].child[i]].dep < trie[trie[u].child[j]].dep;
	});

	for(int i : order) {
		ret.ins(i + 'a');
		dfs(trie[u].child[i]);
		ret.ins('-');
	}
}

void solve() {
	trie.ins(node());
	int n;
	cin >> n;
	foru(i, 1, n) {
		string s;
		cin >> s;
		add(0, 0, s);
	}
	dfs(0);
	while (!ret.empty() && ret.back() == '-') ret.pop_back();
	cout << ret.size() << "\n" << ret;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Line "tptttykduyvxjbzhqupP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 456 KB Line "nP-yerxP----xxvebmcP-------hss...----------labfaryosskugbkiuffdP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Line "hjxgqkP------iupqiqP------rhpq...------------wPfxlmwfirlgbdevjdP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Line "qgjP---tdsP---lbuaP---twxfbhsP...--------------xomsgennpdlurnmvP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Line "wuyP---jPchgP---uegP---ogdcP--...zcbjyszP----------eynorwrbizaiP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1300 KB Line "vPwPjcvP----mhkbP----lscbP----...lP-----------cclviwgdudcybahuwP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5068 KB Line "nPmukluP-----lzwP--hqbvnP-----...-------------zuknicjtukmwmlddzP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 8396 KB Line "nPzPupubP----wdkjkP-----jgqvP-...--------------gPkwzakqubhstcdqP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 29892 KB Line "nPcPgpP--pgnfeP-----alipnP----...------------fmadhysdhsikekrdooP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 16144 KB Line "nPnPzxP--rkP--klP--ceeP---macP...sP----------jbfbP---jtearnhdjeP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -