oj.uz

답안 #518652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518652 2022-01-24T11:14:33 Z Monarchuwu Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 9444 KB 
#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;
}

int num(char c) {
    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;
}

ll calc(int len, int i, int j) {
    if (i != j) {
        if (i > j) swap(i, j);
        return a[len][i][j][0];
    }
    return (a[len][i][j][1] + a[len][i][j][0] * 2) % mod;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;

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

        int i = num(s[0]), j = num(s.back());
        if (i > j) swap(i, j);
        ch.push_back(i);
        ch.push_back(j);

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

    for (int len = 3; len <= 10; ++len)
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j) {
                int i1 = ch[i], i2 = ch[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 < n; ++i1)
            for (int i2 = 0; i2 < n; ++i2)
                for (int i3 = 0; i3 < n; ++i3)
                    for (int i4 = 0; i4 < n; ++i4)
                        for (int i5 = 0; i5 < n; ++i5)
                            for (int i6 = 0; i6 < n; ++i6)
                                for (int i7 = 0; i7 < n; ++i7)
                                    for (int i8 = 0; i8 < n; ++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
**/

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 8328 KB Output is correct
2 Correct 620 ms 9172 KB Output is correct
3 Correct 606 ms 9156 KB Output is correct
4 Correct 598 ms 9172 KB Output is correct
5 Correct 641 ms 9168 KB Output is correct
6 Correct 588 ms 9272 KB Output is correct
7 Correct 595 ms 9168 KB Output is correct
8 Correct 621 ms 9168 KB Output is correct
9 Correct 594 ms 9160 KB Output is correct
10 Correct 612 ms 9160 KB Output is correct
11 Correct 591 ms 9160 KB Output is correct
12 Correct 581 ms 9272 KB Output is correct
13 Correct 625 ms 9164 KB Output is correct
14 Correct 606 ms 9172 KB Output is correct
15 Correct 581 ms 9168 KB Output is correct
16 Correct 600 ms 9168 KB Output is correct
17 Correct 588 ms 9156 KB Output is correct
18 Correct 605 ms 9284 KB Output is correct
19 Correct 627 ms 9196 KB Output is correct
20 Correct 594 ms 9168 KB Output is correct
21 Correct 585 ms 9164 KB Output is correct

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 8328 KB Output is correct
2 Correct 620 ms 9172 KB Output is correct
3 Correct 606 ms 9156 KB Output is correct
4 Correct 598 ms 9172 KB Output is correct
5 Correct 641 ms 9168 KB Output is correct
6 Correct 588 ms 9272 KB Output is correct
7 Correct 595 ms 9168 KB Output is correct
8 Correct 621 ms 9168 KB Output is correct
9 Correct 594 ms 9160 KB Output is correct
10 Correct 612 ms 9160 KB Output is correct
11 Correct 591 ms 9160 KB Output is correct
12 Correct 581 ms 9272 KB Output is correct
13 Correct 625 ms 9164 KB Output is correct
14 Correct 606 ms 9172 KB Output is correct
15 Correct 581 ms 9168 KB Output is correct
16 Correct 600 ms 9168 KB Output is correct
17 Correct 588 ms 9156 KB Output is correct
18 Correct 605 ms 9284 KB Output is correct
19 Correct 627 ms 9196 KB Output is correct
20 Correct 594 ms 9168 KB Output is correct
21 Correct 585 ms 9164 KB Output is correct
22 Execution timed out 1142 ms 9444 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 8328 KB Output is correct
2 Correct 620 ms 9172 KB Output is correct
3 Correct 606 ms 9156 KB Output is correct
4 Correct 598 ms 9172 KB Output is correct
5 Correct 641 ms 9168 KB Output is correct
6 Correct 588 ms 9272 KB Output is correct
7 Correct 595 ms 9168 KB Output is correct
8 Correct 621 ms 9168 KB Output is correct
9 Correct 594 ms 9160 KB Output is correct
10 Correct 612 ms 9160 KB Output is correct
11 Correct 591 ms 9160 KB Output is correct
12 Correct 581 ms 9272 KB Output is correct
13 Correct 625 ms 9164 KB Output is correct
14 Correct 606 ms 9172 KB Output is correct
15 Correct 581 ms 9168 KB Output is correct
16 Correct 600 ms 9168 KB Output is correct
17 Correct 588 ms 9156 KB Output is correct
18 Correct 605 ms 9284 KB Output is correct
19 Correct 627 ms 9196 KB Output is correct
20 Correct 594 ms 9168 KB Output is correct
21 Correct 585 ms 9164 KB Output is correct
22 Execution timed out 1142 ms 9444 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 8328 KB Output is correct
2 Correct 620 ms 9172 KB Output is correct
3 Correct 606 ms 9156 KB Output is correct
4 Correct 598 ms 9172 KB Output is correct
5 Correct 641 ms 9168 KB Output is correct
6 Correct 588 ms 9272 KB Output is correct
7 Correct 595 ms 9168 KB Output is correct
8 Correct 621 ms 9168 KB Output is correct
9 Correct 594 ms 9160 KB Output is correct
10 Correct 612 ms 9160 KB Output is correct
11 Correct 591 ms 9160 KB Output is correct
12 Correct 581 ms 9272 KB Output is correct
13 Correct 625 ms 9164 KB Output is correct
14 Correct 606 ms 9172 KB Output is correct
15 Correct 581 ms 9168 KB Output is correct
16 Correct 600 ms 9168 KB Output is correct
17 Correct 588 ms 9156 KB Output is correct
18 Correct 605 ms 9284 KB Output is correct
19 Correct 627 ms 9196 KB Output is correct
20 Correct 594 ms 9168 KB Output is correct
21 Correct 585 ms 9164 KB Output is correct
22 Execution timed out 1142 ms 9444 KB Time limit exceeded
23 Halted 0 ms 0 KB -