Submission #211818

#	Time	Username	Problem	Language	Result	Execution time	Memory
211818		spdskatr	Cubeword (CEOI19_cubeword)	C++14	100 / 100	443 ms	23676 KiB

cubeword

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <string>
    #include <cstring>
    #include <iostream>
    #include <vector>
    #include <set>
    #define M 998244353
    using namespace std;
    typedef long long ll;
     
    int N, gr[100005][10], npal[100005];
    ll dp[64][64][64], tot[64][64][64], cnt[64][64], ans;
    string s;
    set<string> ss;
    vector<int> tal[11];
     
    int conv(char c) {
    	if ('a' <= c && c <= 'z') return c - 'a';
    	if ('A' <= c && c <= 'Z') return (c - 'A') + 26;
    	return (c - '0') + 52;
    }
     
    ll pm(ll x, ll y) {
    	return (x * y) % M;
    }
     
    int main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    	cin >> N;
    	for (int i = 0; i < N; i++) {
    		cin >> s;
    		for (int j = 0; j < s.size(); j++) {
    			gr[i][j] = conv(s[j]);
    		}
    		for (int j = 0; j <= s.size() / 2; j++) {
    			if (s[j] != s[s.size() - 1 - j]) npal[i] = 1;
    		}
    		if (ss.find(s) == ss.end()) {
    			ss.emplace(s);
    			reverse(s.begin(), s.end());
    			ss.emplace(s);
    			tal[s.size()].push_back(i);
    		}
    	}
    	for (int n = 3; n <= 10; n++) {
    		memset(dp, 0, sizeof(dp));
    		memset(cnt, 0, sizeof(cnt));
    		for (int i : tal[n]) {
    			if (npal[i]) {
    				cnt[gr[i][0]][gr[i][n-1]]++;
    				cnt[gr[i][n-1]][gr[i][0]]++;
    			} else {
    				cnt[gr[i][0]][gr[i][n-1]]++;
    			}
    		}
    		for (int a = 0; a < 62; a++) for (int b = a; b < 62; b++) for (int c = b; c < 62; c++) for (int x = 0; x < 62; x++) {
    			dp[a][b][c] = (dp[a][b][c] + pm(cnt[x][a], pm(cnt[x][b], cnt[x][c]))) % M;
    		}
    		for (int a = 0; a < 62; a++) for (int b = a; b < 62; b++) for (int c = b; c < 62; c++) for (int d = c; d < 62; d++) {
    			int fac = 24;
    			if (a == b) {
    				if (b == c) {
    					if (c == d) fac = 1;
    					else fac = 4;
    				} else {
    					if (c == d) fac = 6;
    					else fac = 12;
    				}
    			} else {
    				if (b == c) {
    					if (c == d) fac = 4;
    					else fac = 12;
    				} else {
    					if (c == d) fac = 12;
    					else fac = 24;
    				}
    			}
    			ll pans = ans;
    			ans = (ans + pm(fac, pm(pm(dp[a][b][d], dp[a][b][c]), pm(dp[a][c][d], dp[b][c][d]))))%M;
    		}
    	}
    	cout << ans;
    	return 0;
    }

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:35:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < s.size(); j++) {
                       ~~^~~~~~~~~~
cubeword.cpp:38:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j <= s.size() / 2; j++) {
                       ~~^~~~~~~~~~~~~~~
cubeword.cpp:81:11: warning: unused variable 'pans' [-Wunused-variable]
        ll pans = ans;
           ^~~~

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