Submission #1308380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308380		a5a7	Type Printer (IOI08_printer)	C++20	100 / 100	72 ms	50056 KiB

printer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int trie[1000000][26];
bool stop[1000000];
int nodes = 1;
string longest;
vector<char> operations;

void add(string s){
    int current = 0;
    int cnt = 0;
    for (char c : s){
        if (trie[current][c-'a'] == 0){
            trie[current][c-'a'] = nodes++;
        }
        cnt++;
        current = trie[current][c-'a'];
    }
    stop[current] = true;
}

void search(int current, int pos){
    int num = pos >= int(longest.size()) ? -1 : longest[pos]-'a';
    if (stop[current]){
        operations.push_back('P');
    }
    int old_current = current;
    for (int i = 0; i < 26; i++){
        if (i == num) continue;
        if (trie[current][i] == 0) continue;
        operations.push_back(char(i + 'a'));
        current = trie[current][i];
        search(current, pos+1);
        operations.push_back('-');
        current = old_current;
    }
    if (num != -1){
        if (trie[current][num] == 0) return;
        operations.push_back(char(num+'a'));
        current = trie[current][num];
        search(current, pos+1);
        current = old_current;
        operations.push_back('-');
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    string s[n];
    for (int i = 0; i < n; i++){
        cin >> s[i];
        add(s[i]);
    }
    longest = s[0];
    for (int i = 1; i < n; i++){
        if (longest.size() < s[i].size()) longest = s[i];
    }
    search(0, 0);
    while (operations.back() != 'P') operations.pop_back();
    cout << operations.size() << endl;
    for (char c : operations) cout << c << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10