Submission #518648

#	Time	Username	Problem	Language	Result	Execution time	Memory
518648		Monarchuwu	Cubeword (CEOI19_cubeword)	C++17	0 / 100	265 ms	9172 KiB

cubeword

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_set>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e5 + 9, mod = 998244353;
int n;
int a[11][62][62][2];

bool palind(string s) {
    int l(0), r(s.size() - 1);
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l, --r;
    }
    return true;
}

vector<int> ch;
bool flag;
int num(char c) {
    if (!flag) {
        if ('a' <= c && c <= 'z') return c - 'a';
        if ('A' <= c && c <= 'Z') return c - 'A' + 26;
        if ('0' <= c && c <= '9') return c - '0' + 52;
        return -1;
    }
    else {
        return lower_bound(all(ch), c) - ch.begin();
    }
}

ll pw[N];
ll calc(int len, int i, int j) {
    if (i > j) swap(i, j);
    return a[len][i][j][0] + pw[a[len][i][j][1]];
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    pw[1] = 2;
    for (int i = 2; i <= n; ++i) {
        pw[i] = pw[i - 1] << 1;
        if (pw[i] > mod) pw[i] -= mod;
    }

    unordered_set<string> S;
    for (int ii = 0; ii < n; ++ii) {
        string s; cin >> s;
        if (S.count(s)) continue;

        char c1(s[0]), c2(s.back());
        ch.push_back(num(c1));
        ch.push_back(num(c2));

        int i = num(c1), j = num(c2);
        if (i > j) swap(i, j);

        ++a[s.size()][i][j][palind(s)];
        reverse(all(s));
        S.insert(s);
    }
    sort(all(ch));
    ch.resize(unique(all(ch)) - ch.begin());
    flag = true;

    for (int len = 3; len <= 10; ++len)
        for (int i1 = 0; i1 < 62; ++i1)
            for (int i2 = 0; i2 < 62; ++i2) {
                int i = num(i1), j = num(i2);
                if (i > j) swap(i, j);
                a[len][i][j][0] = a[len][i1][i2][0];
                a[len][i][j][1] = a[len][i1][i2][1];
            }

    ll ans(0);
    for (int len = 3; len <= 10; ++len)
        for (int i1 = 0; i1 < ch.size(); ++i1)
            for (int i2 = 0; i2 < ch.size(); ++i2)
                for (int i3 = 0; i3 < ch.size(); ++i3)
                    for (int i4 = 0; i4 < ch.size(); ++i4)
                        for (int i5 = 0; i5 < ch.size(); ++i5)
                            for (int i6 = 0; i6 < ch.size(); ++i6)
                                for (int i7 = 0; i7 < ch.size(); ++i7)
                                    for (int i8 = 0; i8 < ch.size(); ++i8) {
                                        ans += calc(len, i1, i2) * calc(len, i2, i3) % mod * calc(len, i3, i4) % mod * calc(len, i4, i1) % mod
                                            * calc(len, i1, i5) % mod * calc(len, i2, i6) % mod * calc(len, i3, i7) % mod * calc(len, i4, i8) % mod
                                            * calc(len, i5, i6) % mod * calc(len, i6, i7) % mod * calc(len, i7, i8) % mod * calc(len, i8, i5);
                                        ans %= mod;
                                    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:83:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i1 = 0; i1 < ch.size(); ++i1)
      |                          ~~~^~~~~~~~~~~
cubeword.cpp:84:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for (int i2 = 0; i2 < ch.size(); ++i2)
      |                              ~~~^~~~~~~~~~~
cubeword.cpp:85:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for (int i3 = 0; i3 < ch.size(); ++i3)
      |                                  ~~~^~~~~~~~~~~
cubeword.cpp:86:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                     for (int i4 = 0; i4 < ch.size(); ++i4)
      |                                      ~~~^~~~~~~~~~~
cubeword.cpp:87:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                         for (int i5 = 0; i5 < ch.size(); ++i5)
      |                                          ~~~^~~~~~~~~~~
cubeword.cpp:88:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                             for (int i6 = 0; i6 < ch.size(); ++i6)
      |                                              ~~~^~~~~~~~~~~
cubeword.cpp:89:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                                 for (int i7 = 0; i7 < ch.size(); ++i7)
      |                                                  ~~~^~~~~~~~~~~
cubeword.cpp:90:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                                     for (int i8 = 0; i8 < ch.size(); ++i8) {
      |                                                      ~~~^~~~~~~~~~~

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