Submission #546590

#	Time	Username	Problem	Language	Result	Execution time	Memory
546590		LucaDantas	Cubeword (CEOI19_cubeword)	C++17	50 / 100	447 ms	17524 KiB

cubeword

#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 16, mod = 998244353; // subtasks 1-2

int ans;

int edge[11][maxn][maxn];

int value_triad[11][maxn][maxn][maxn];

int id(char c) { return c-'a'; } // subtaks 1-2

set<string> mark;

void add(int& a, int b) { a += b; if(a >= mod) a -= mod; }

int main() {
    int n; cin >> n;
    string s;
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int rep = 0; rep < 2; rep++, reverse(s.begin(), s.end())) if(!mark.count(s)) {
            edge[s.size()][id(s[0])][id(s.back())]++;
            mark.insert(s);
        }
    }

    vector<array<int,4>> quad;
    for(int a = 0; a < maxn; a++) for(int b = 0; b < maxn; b++) for(int c = 0; c < maxn; c++) for(int d = 0; d < maxn; d++)
        quad.push_back({a, b, c, d});

    for(int sz = 3; sz <= 10; sz++) for(int i = 0; i < quad.size(); i++) {
        int aq = 0, dp = 1;
        for(int rep = 0; rep < 4; rep++) {
            for(int x = 0; x < maxn; x++) {
                int hm = 1;
                for(int ind = 0; ind < 4; ind++) if(ind != rep)
                    hm = 1ll * hm * edge[sz][x][quad[i][ind]] % mod;
                add(aq, hm);
            }
            dp = 1ll * dp * aq % mod;
            aq = 0;
        }
        add(ans, dp);
    }

    printf("%d\n", ans);
}

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:36:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int sz = 3; sz <= 10; sz++) for(int i = 0; i < quad.size(); i++) {
      |                                                    ~~^~~~~~~~~~~~~

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