Submission #941939

#	Time	Username	Problem	Language	Result	Execution time	Memory
941939		MuntherCarrot	Palindromes (APIO14_palindrome)	C++14	0 / 100	44 ms	69036 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define INFLL (ll)0x3f3f3f3f3f3f3f3f
const int MOD = 1e9 + 7, SZ = 1e5 + 10;

// Trie v0.1
struct trie{
    vector<vector<int>> Trie;
    vector<int> End;
    vector<char> ans;
    int MAXN, node_cnt;
    string big;
    trie(int N) : MAXN(N), node_cnt(0) {
        Trie.resize(MAXN, vector<int>(26));
        End.resize(MAXN);
    }
    void insert(string &word){
        int node = 0;
        for(int i = 0; i < word.size(); i++){
            if(Trie[node][word[i] - 'a'] == 0){
                Trie[node][word[i] - 'a'] = ++node_cnt;
            }
            node = Trie[node][word[i] - 'a'];
        }
        End[node]++;
    }
    void solve(int node = 0, int x = 0){
        for(int i = 0; i < End[node]; i++){
            ans.push_back('P');
        }
        for(int i = 0; i < 26; i++){
            if(x != -1 && (char)('a' + i) == big[x]) continue;
            if(Trie[node][i] == 0) continue;
            ans.push_back((char)('a' + i));
            solve(Trie[node][i], -1);
            ans.push_back('-');
        }
        if(x != -1 && x != big.size()){
            ans.push_back(big[x]);
            solve(Trie[node][big[x] - 'a'], x + 1);
        }
    }
} Trie(25000 * 20);

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, mx = 0;
    cin >> n;
    string s[n];
    for(auto &i : s){
        cin >> i;
        Trie.insert(i);
        if(mx < i.size()){
            mx = i.size();
            Trie.big = i;
        }
    }
    Trie.solve();
    cout << Trie.ans.size() << endl;
    // cout << Trie.ans.size() - mx << endl;
    for(int i = 0; i < Trie.ans.size(); i++){
        cout << Trie.ans[i] << endl;
    }
    return 0;
}
// by me

Compilation message (stderr)

palindrome.cpp: In member function 'void trie::insert(std::string&)':
palindrome.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i = 0; i < word.size(); i++){
      |                        ~~^~~~~~~~~~~~~
palindrome.cpp: In member function 'void trie::solve(int, int)':
palindrome.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(x != -1 && x != big.size()){
      |                       ~~^~~~~~~~~~~~~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(mx < i.size()){
      |            ~~~^~~~~~~~~~
palindrome.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < Trie.ans.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27