oj.uz

Submission #276043

# Submission time Handle Problem Language Result Execution time Memory
276043 2020-08-20T10:11:11 Z theStaticMind Cubeword (CEOI19_cubeword) C++14
21 / 100
 381 ms 15396 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

const int k = 8;

int dp[k][k][k][k];
int dp2[k][k][k][k];
int dp3[k][k][k][k];

map<char, int> ptr;

void clear(){
	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					dp[a][b][c][d] = 0;
					dp2[a][b][c][d] = 0;
					dp3[a][b][c][d] = 0;
				}
			}
		}
	}
}
 
int solve(map<ii, int>& cnt){

	clear();

	/*for(auto p : cnt){
		cout << p.first.first << "-" << p.first.second << "=>" << p.second << "\n";
	}*/

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					dp[a][b][c][d] = cnt[{a, b}] * cnt[{b, d}] % mod * cnt[{d, c}] % mod * cnt[{c, a}] % mod;
				}
			}
		}
	}

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					for(int e = 0; e < k; e++){
						for(int f = 0; f < k; f++){
							dp2[a][b][e][f] += dp[c][d][e][f] * cnt[{a, c}] % mod * cnt[{b, d}] % mod * cnt[{a, b}] % mod;
							dp2[a][b][e][f] %= mod;
						}
					}
				}
			}
		}
	}

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					for(int e = 0; e < k; e++){
						for(int f = 0; f < k; f++){
							dp3[a][b][e][f] += dp2[c][d][e][f] * cnt[{a, c}] % mod * cnt[{b, d}] % mod * cnt[{a, b}] % mod;
							dp3[a][b][e][f] %= mod;
						}
					}
				}
			}
		}
	}

	int ret = 0;

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					ret += dp3[a][b][c][d] * cnt[{a, c}] % mod * cnt[{b, d}];
					ret %= mod;
				}
			}
		}
	}

	return ret;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, ans = 0;
	cin >> n;

	unordered_set<string> S[11];
	vector<string> arr;

	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		S[sz(s)].insert(s);
		reverse(all(s));
		S[sz(s)].insert(s);
	}

	for(char i = 'a'; i <= 'p'; i++) ptr[i] = 0;
//	for(char i = 'A'; i <= 'P'; i++) ptr[i] = 0;

	int ind = 0;
	for(auto& p : ptr){
		p.second = ind++;
	}

	for(int i = 3; i <= 10; i++){ 
		if(S[i].empty()) continue;
		map<ii, int> cnt;
		for(auto p : S[i]){
			cnt[{ptr[p[0]], ptr[p[i - 1]]}]++;
		}

		ans += solve(cnt);
	}

	cout << ans % mod;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 15280 KB Output is correct
2 Correct 340 ms 15364 KB Output is correct
3 Correct 337 ms 15272 KB Output is correct
4 Correct 359 ms 15276 KB Output is correct
5 Correct 343 ms 15272 KB Output is correct
6 Correct 337 ms 15272 KB Output is correct
7 Correct 333 ms 15272 KB Output is correct
8 Correct 373 ms 15240 KB Output is correct
9 Correct 325 ms 15272 KB Output is correct
10 Correct 377 ms 15272 KB Output is correct
11 Correct 354 ms 15300 KB Output is correct
12 Correct 342 ms 15232 KB Output is correct
13 Correct 369 ms 15396 KB Output is correct
14 Correct 348 ms 15348 KB Output is correct
15 Correct 345 ms 15284 KB Output is correct
16 Correct 342 ms 15288 KB Output is correct
17 Correct 326 ms 15304 KB Output is correct
18 Correct 338 ms 15160 KB Output is correct
19 Correct 347 ms 15148 KB Output is correct
20 Correct 344 ms 15272 KB Output is correct
21 Correct 339 ms 15272 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 15280 KB Output is correct
2 Correct 340 ms 15364 KB Output is correct
3 Correct 337 ms 15272 KB Output is correct
4 Correct 359 ms 15276 KB Output is correct
5 Correct 343 ms 15272 KB Output is correct
6 Correct 337 ms 15272 KB Output is correct
7 Correct 333 ms 15272 KB Output is correct
8 Correct 373 ms 15240 KB Output is correct
9 Correct 325 ms 15272 KB Output is correct
10 Correct 377 ms 15272 KB Output is correct
11 Correct 354 ms 15300 KB Output is correct
12 Correct 342 ms 15232 KB Output is correct
13 Correct 369 ms 15396 KB Output is correct
14 Correct 348 ms 15348 KB Output is correct
15 Correct 345 ms 15284 KB Output is correct
16 Correct 342 ms 15288 KB Output is correct
17 Correct 326 ms 15304 KB Output is correct
18 Correct 338 ms 15160 KB Output is correct
19 Correct 347 ms 15148 KB Output is correct
20 Correct 344 ms 15272 KB Output is correct
21 Correct 339 ms 15272 KB Output is correct
22 Incorrect 381 ms 15224 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 15280 KB Output is correct
2 Correct 340 ms 15364 KB Output is correct
3 Correct 337 ms 15272 KB Output is correct
4 Correct 359 ms 15276 KB Output is correct
5 Correct 343 ms 15272 KB Output is correct
6 Correct 337 ms 15272 KB Output is correct
7 Correct 333 ms 15272 KB Output is correct
8 Correct 373 ms 15240 KB Output is correct
9 Correct 325 ms 15272 KB Output is correct
10 Correct 377 ms 15272 KB Output is correct
11 Correct 354 ms 15300 KB Output is correct
12 Correct 342 ms 15232 KB Output is correct
13 Correct 369 ms 15396 KB Output is correct
14 Correct 348 ms 15348 KB Output is correct
15 Correct 345 ms 15284 KB Output is correct
16 Correct 342 ms 15288 KB Output is correct
17 Correct 326 ms 15304 KB Output is correct
18 Correct 338 ms 15160 KB Output is correct
19 Correct 347 ms 15148 KB Output is correct
20 Correct 344 ms 15272 KB Output is correct
21 Correct 339 ms 15272 KB Output is correct
22 Incorrect 381 ms 15224 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 15280 KB Output is correct
2 Correct 340 ms 15364 KB Output is correct
3 Correct 337 ms 15272 KB Output is correct
4 Correct 359 ms 15276 KB Output is correct
5 Correct 343 ms 15272 KB Output is correct
6 Correct 337 ms 15272 KB Output is correct
7 Correct 333 ms 15272 KB Output is correct
8 Correct 373 ms 15240 KB Output is correct
9 Correct 325 ms 15272 KB Output is correct
10 Correct 377 ms 15272 KB Output is correct
11 Correct 354 ms 15300 KB Output is correct
12 Correct 342 ms 15232 KB Output is correct
13 Correct 369 ms 15396 KB Output is correct
14 Correct 348 ms 15348 KB Output is correct
15 Correct 345 ms 15284 KB Output is correct
16 Correct 342 ms 15288 KB Output is correct
17 Correct 326 ms 15304 KB Output is correct
18 Correct 338 ms 15160 KB Output is correct
19 Correct 347 ms 15148 KB Output is correct
20 Correct 344 ms 15272 KB Output is correct
21 Correct 339 ms 15272 KB Output is correct
22 Incorrect 381 ms 15224 KB Output isn't correct
23 Halted 0 ms 0 KB -