# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
303794 | FlashGamezzz | Type Printer (IOI08_printer) | C++17 | 261 ms | 64968 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
vector<int> lets[500000];
bool endb[500000] = {};
int length[500000] = {}, sz = 0;
vector<char> ans;
void add(int c, int i, string s){
if (i == s.length()){
endb[c] = true; return;
}
int l = int(s[i])-97;
if (lets[c][l] == 0){
vector<int> t; t.resize(26, 0); lets[sz] = t;
lets[c][l] = sz; sz++;
}
add(lets[c][l], i+1, s);
length[c] = max(length[lets[c][l]]+1, length[c]);
}
void solve(long c){
if (endb[c]){
ans.push_back('P');
}
bool lu = false; int dl = -1;
for (int i = 0; i < 26; i++){
if (lets[c][i] != 0){
if (!lu && length[lets[c][i]] == length[c]-1){
lu = true; dl = i;
} else {
ans.push_back(char(i+97));
solve(lets[c][i]);
ans.push_back('-');
}
}
}
if (dl > -1){
ans.push_back(char(dl+97));
solve(lets[c][dl]);
ans.push_back('-');
}
}
int main(){
int n; cin >> n;
vector<int> t; t.resize(26, 0); lets[sz] = t; sz++;
for (int i = 0; i < n; i++){
string s; cin >> s;
add(0, 0, s);
}
solve(0);
int count = ans.size();
while (ans[count-1] == '-'){
count--;
}
printf("%d\n", count);
for (int i = 0; i < count-1; i++){
printf("%c\n", ans[i]);
}
printf("%c", ans[count-1]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |