Submission #501022

#	Time	Username	Problem	Language	Result	Execution time	Memory
501022		InternetPerson10	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1010 ms	9328 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll MOD = 998244353;

ll ct[200][200];
int ch[4];

string s1 = "abcdef";
string s2 = "abcdefghijklmnop";
string s3 = "abcdefghijklmnopABCDEFGHIJKLMNOP";
string s4 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

unordered_map<int, ll> m;

ll conv(ll b, ll c, ll d) {
    return 40000LL * b + 200LL * c + d;
}

ll rec(int i) {
    if(i == 4) {
        ll ans = 1;
        ans *= m[conv(ch[0], ch[1], ch[2])];
        if(ans > MOD) ans %= MOD;
        ans *= m[conv(ch[0], ch[1], ch[3])];
        if(ans > MOD) ans %= MOD;
        ans *= m[conv(ch[0], ch[2], ch[3])];
        if(ans > MOD) ans %= MOD;
        ans *= m[conv(ch[1], ch[2], ch[3])];
        if(ans > MOD) ans %= MOD;
        if(ans) cout << ch[0] << ' ' << ch[1] << ' ' << ch[2] << ' ' << ch[3] << ' ' << ans << '\n';
        return ans;
    }
    ll ans = 0;
    int k = 0;
    if(i) {
        for(int j = 0; j < s4.size(); j++) {
            if(s4.at(j) == ch[i-1]) k = j;
        }
    }
    for(int j = k; j < s4.size(); j++) {
        ch[i] = (int)s4.at(j);
        ans += rec(i+1);
        if(ans > MOD) ans %= MOD;
    }
    return ans;
}

ll perms(int a, int b, int c, int d) {
    if(a == b && b == c && c == d) return 1;
    if(a == b && b == c) return 4;
    if(b == c && c == d) return 4;
    if(a == b && c == d) return 6;
    if(a == b || b == c || c == d) return 12;
    return 24;
}

int main() {
    int n;
    cin >> n;
    vector<string> words(n), v;
    set<string> s;
    for(int i = 0; i < n; i++) {
        cin >> words[i];
    }
    ll ans = 0;
    for(int x = 3; x <= 10; x++) {
        for(int i = 0; i < n; i++) {
            if(words[i].size() == x) v.push_back(words[i]);
        }
        for(int i = 0; i < v.size(); i++) {
            if(s.count(v[i])) continue;
            s.insert(v[i]);
            ct[v[i][0]][v[i][v[i].size()-1]]++;
            // Other side
            reverse(v[i].begin(), v[i].end());
            if(s.count(v[i])) continue;
            s.insert(v[i]);
            ct[v[i][0]][v[i][v[i].size()-1]]++;
        }
        for(int i = 0; i < s4.size(); i++) {
            for(int j = i; j < s4.size(); j++) {
                for(int k = j; k < s4.size(); k++) {
                    for(int l = 0; l < s4.size(); l++) {
                        int w = s4[i], x = s4[j], y = s4[k], z = s4[l];
                        ll g = (ct[w][z] * ct[x][z] * ct[y][z]) % MOD;
                        if(g == 0) continue;
                        m[conv(w, x, y)] += g; 
                        m[conv(w, x, y)] %= MOD;
                    }
                }
            }
        }
        for(int i = 0; i < s4.size(); i++) {
            for(int j = i; j < s4.size(); j++) {
                for(int k = j; k < s4.size(); k++) {
                    for(int l = k; l < s4.size(); l++) {
                        ll tot = 1;
                        tot *= m[conv(s4[i], s4[j], s4[k])];
                        tot *= m[conv(s4[i], s4[j], s4[l])];
                        tot %= MOD;
                        tot *= m[conv(s4[i], s4[k], s4[l])];
                        tot %= MOD;
                        tot *= m[conv(s4[j], s4[k], s4[l])];
                        tot %= MOD;
                        tot *= perms(i, j, k, l);
                        ans += tot;
                        ans %= MOD;
                    }
                }
            }
        }
        for(int i = 0; i < v.size(); i++) {
            ct[v[i][0]][v[i][v[i].size()-1]] = 0;
            reverse(v[i].begin(), v[i].end());
            ct[v[i][0]][v[i][v[i].size()-1]] = 0;
        }
        vector<string>().swap(v);
        set<string>().swap(s);
        unordered_map<int, ll>().swap(m);
    }
    cout << ans << '\n';
}

Compilation message (stderr)

cubeword.cpp: In function 'll rec(int)':
cubeword.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j = 0; j < s4.size(); j++) {
      |                        ~~^~~~~~~~~~~
cubeword.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j = k; j < s4.size(); j++) {
      |                    ~~^~~~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:71:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |             if(words[i].size() == x) v.push_back(words[i]);
      |                ~~~~~~~~~~~~~~~~^~~~
cubeword.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < v.size(); i++) {
      |                        ~~^~~~~~~~~~
cubeword.cpp:76:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |             ct[v[i][0]][v[i][v[i].size()-1]]++;
      |                       ^
cubeword.cpp:76:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |             ct[v[i][0]][v[i][v[i].size()-1]]++;
      |                                            ^
cubeword.cpp:81:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |             ct[v[i][0]][v[i][v[i].size()-1]]++;
      |                       ^
cubeword.cpp:81:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |             ct[v[i][0]][v[i][v[i].size()-1]]++;
      |                                            ^
cubeword.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0; i < s4.size(); i++) {
      |                        ~~^~~~~~~~~~~
cubeword.cpp:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(int j = i; j < s4.size(); j++) {
      |                            ~~^~~~~~~~~~~
cubeword.cpp:85:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for(int k = j; k < s4.size(); k++) {
      |                                ~~^~~~~~~~~~~
cubeword.cpp:86:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                     for(int l = 0; l < s4.size(); l++) {
      |                                    ~~^~~~~~~~~~~
cubeword.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i = 0; i < s4.size(); i++) {
      |                        ~~^~~~~~~~~~~
cubeword.cpp:97:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(int j = i; j < s4.size(); j++) {
      |                            ~~^~~~~~~~~~~
cubeword.cpp:98:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for(int k = j; k < s4.size(); k++) {
      |                                ~~^~~~~~~~~~~
cubeword.cpp:99:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                     for(int l = k; l < s4.size(); l++) {
      |                                    ~~^~~~~~~~~~~
cubeword.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int i = 0; i < v.size(); i++) {
      |                        ~~^~~~~~~~~~
cubeword.cpp:116:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  116 |             ct[v[i][0]][v[i][v[i].size()-1]] = 0;
      |                       ^
cubeword.cpp:116:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  116 |             ct[v[i][0]][v[i][v[i].size()-1]] = 0;
      |                                            ^
cubeword.cpp:118:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |             ct[v[i][0]][v[i][v[i].size()-1]] = 0;
      |                       ^
cubeword.cpp:118:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |             ct[v[i][0]][v[i][v[i].size()-1]] = 0;
      |                                            ^

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 16 / 16