oj.uz

답안 #572330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572330 2022-06-04T09:15:46 Z piOOE Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 8664 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 8, A = 'p' - 'a' + 1, L = 11, mod = 998244353;
const ll infL = 3e18;

int g[N][3] = {{1, 2, 4},
               {0, 3, 5},
               {0, 3, 6},
               {1, 2, 7},
               {0, 5, 6},
               {1, 4, 7},
               {2, 4, 7},
               {3, 5, 6}};

int n;
int cnt[A][A][L], used[N];
int ans = 0, len = 0;

void rec(int i, int val) {
    if (val == 0) {
        return;
    }
    if (i == N) {
        ans = (ans + val) % mod;
        return;
    }
    for (int x = 0; x < A; ++x) {
        used[i] = x;
        int nw = val;
        for (int to: g[i]) {
            if (used[to] == -1) continue;
            nw = (nw * (ll) cnt[used[i]][used[to]][len]) % mod;
        }
        rec(i + 1, nw);
    }
    used[i] = -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<string> stt;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        string ss = s;
        reverse(all(ss));
        stt.push_back(ss);
        stt.push_back(s);
    }
    sort(all(stt));
    stt.resize(unique(all(stt)) - begin(stt));
    for (string s: stt) {
        ++cnt[s[0] - 'a'][s.back() - 'a'][sz(s)];
    }
    memset(used, -1, sizeof(used));
    for (len = 1; len < L; ++len) {
        rec(0, 1);
    }
    cout << ans;
    return 0;
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 572 ms 8648 KB Output is correct
2 Correct 548 ms 8648 KB Output is correct
3 Correct 558 ms 8648 KB Output is correct
4 Correct 572 ms 8652 KB Output is correct
5 Correct 578 ms 8648 KB Output is correct
6 Correct 583 ms 8648 KB Output is correct
7 Correct 624 ms 8648 KB Output is correct
8 Correct 584 ms 8648 KB Output is correct
9 Correct 551 ms 8664 KB Output is correct
10 Correct 567 ms 8648 KB Output is correct
11 Correct 556 ms 8648 KB Output is correct
12 Correct 551 ms 8648 KB Output is correct
13 Correct 609 ms 8612 KB Output is correct
14 Correct 562 ms 8648 KB Output is correct
15 Correct 559 ms 8648 KB Output is correct
16 Correct 584 ms 8648 KB Output is correct
17 Correct 557 ms 8648 KB Output is correct
18 Correct 570 ms 8648 KB Output is correct
19 Correct 555 ms 8648 KB Output is correct
20 Correct 565 ms 8648 KB Output is correct
21 Correct 560 ms 8648 KB Output is correct

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 572 ms 8648 KB Output is correct
2 Correct 548 ms 8648 KB Output is correct
3 Correct 558 ms 8648 KB Output is correct
4 Correct 572 ms 8652 KB Output is correct
5 Correct 578 ms 8648 KB Output is correct
6 Correct 583 ms 8648 KB Output is correct
7 Correct 624 ms 8648 KB Output is correct
8 Correct 584 ms 8648 KB Output is correct
9 Correct 551 ms 8664 KB Output is correct
10 Correct 567 ms 8648 KB Output is correct
11 Correct 556 ms 8648 KB Output is correct
12 Correct 551 ms 8648 KB Output is correct
13 Correct 609 ms 8612 KB Output is correct
14 Correct 562 ms 8648 KB Output is correct
15 Correct 559 ms 8648 KB Output is correct
16 Correct 584 ms 8648 KB Output is correct
17 Correct 557 ms 8648 KB Output is correct
18 Correct 570 ms 8648 KB Output is correct
19 Correct 555 ms 8648 KB Output is correct
20 Correct 565 ms 8648 KB Output is correct
21 Correct 560 ms 8648 KB Output is correct
22 Execution timed out 1190 ms 8648 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 572 ms 8648 KB Output is correct
2 Correct 548 ms 8648 KB Output is correct
3 Correct 558 ms 8648 KB Output is correct
4 Correct 572 ms 8652 KB Output is correct
5 Correct 578 ms 8648 KB Output is correct
6 Correct 583 ms 8648 KB Output is correct
7 Correct 624 ms 8648 KB Output is correct
8 Correct 584 ms 8648 KB Output is correct
9 Correct 551 ms 8664 KB Output is correct
10 Correct 567 ms 8648 KB Output is correct
11 Correct 556 ms 8648 KB Output is correct
12 Correct 551 ms 8648 KB Output is correct
13 Correct 609 ms 8612 KB Output is correct
14 Correct 562 ms 8648 KB Output is correct
15 Correct 559 ms 8648 KB Output is correct
16 Correct 584 ms 8648 KB Output is correct
17 Correct 557 ms 8648 KB Output is correct
18 Correct 570 ms 8648 KB Output is correct
19 Correct 555 ms 8648 KB Output is correct
20 Correct 565 ms 8648 KB Output is correct
21 Correct 560 ms 8648 KB Output is correct
22 Execution timed out 1190 ms 8648 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 572 ms 8648 KB Output is correct
2 Correct 548 ms 8648 KB Output is correct
3 Correct 558 ms 8648 KB Output is correct
4 Correct 572 ms 8652 KB Output is correct
5 Correct 578 ms 8648 KB Output is correct
6 Correct 583 ms 8648 KB Output is correct
7 Correct 624 ms 8648 KB Output is correct
8 Correct 584 ms 8648 KB Output is correct
9 Correct 551 ms 8664 KB Output is correct
10 Correct 567 ms 8648 KB Output is correct
11 Correct 556 ms 8648 KB Output is correct
12 Correct 551 ms 8648 KB Output is correct
13 Correct 609 ms 8612 KB Output is correct
14 Correct 562 ms 8648 KB Output is correct
15 Correct 559 ms 8648 KB Output is correct
16 Correct 584 ms 8648 KB Output is correct
17 Correct 557 ms 8648 KB Output is correct
18 Correct 570 ms 8648 KB Output is correct
19 Correct 555 ms 8648 KB Output is correct
20 Correct 565 ms 8648 KB Output is correct
21 Correct 560 ms 8648 KB Output is correct
22 Execution timed out 1190 ms 8648 KB Time limit exceeded
23 Halted 0 ms 0 KB -