oj.uz

Submission #447056

# Submission time Handle Problem Language Result Execution time Memory
447056 2021-07-24T10:55:32 Z fhvirus Cubeword (CEOI19_cubeword) C++17
84 / 100
 1100 ms 65448 KB 
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif
 
const int kC = 62;
const int MOD = 998244353;
inline int ci(char c){ return c >= 'a' ? c - 'a' : (c >= 'A' ? c - 'A' + 26 : c - '0' + 52); }
inline void mad(int &a, int b){ a += b - MOD; a += (a>>31) & MOD; }
 
int adj[kC][kC];
int tri[kC][kC][kC];
int qua[kC][kC][kC][kC];
void init(){
	memset(adj, 0, sizeof(adj));
	memset(tri, 0, sizeof(tri));
	memset(qua, 0, sizeof(qua));
}
 
bool isPalim(string s){
	int n = s.size();
	for(int l = 0, r = n-1; l < r; ++l, --r)
		if(s[l] != s[r]) return false;
	return true;
}
 
int solve(vector<string> &s){
	debug(s);
	if(s.empty()) return 0;
	init();
	set<string> ss;
	for(auto i: s){
		if(ss.count(i)) continue;
		int a = ci(i.front()), b = ci(i.back());
		ss.insert(i);
		++adj[a][b];
		if(isPalim(i)) continue;
		reverse(AI(i));
		ss.insert(i);
		++adj[b][a];
	}
 
//	for(int i = 0; i < kC; ++i){
//		for(int j = 0; j < kC; ++j)
//			cout << adj[i][j] << ' ';
//		cout << '\n';
//	}
 
	// construct tri
	for(int u = 0; u < kC; ++u)
		for(int i = 0; i < kC; ++i) if(adj[u][i])
			for(int j = i; j < kC; ++j) if(adj[u][j])
				for(int k = j; k < kC; ++k) if(adj[u][k]){
					int v = 1ll * adj[i][u] * adj[j][u] * adj[k][u] % MOD;
					vector<int> a = {i, j, k};
					do mad(tri[a[0]][a[1]][a[2]], v); while(next_permutation(AI(a)));
				}
 
	// construct qua
	for(int i = 0; i < kC; ++i)
		for(int j = 0; j < kC; ++j)
			for(int k = j; k < kC; ++k) if(tri[i][j][k])
				for(int l = i; l < kC; ++l) if(tri[j][k][l]){
					int v = 1ll * tri[i][j][k] * tri[j][k][l] % MOD;
					mad(qua[i][j][k][l], v);
					if(k != j) mad(qua[i][k][j][l], v);
					if(i != l) mad(qua[l][j][k][i], v);
					if(i != l and k != j) mad(qua[l][k][j][i], v);
				}
 
	int ans = 0;
	for(int i = 0; i < kC; ++i)
		for(int j = i; j < kC; ++j)
			for(int k = 0; k < kC; ++k)
				for(int l = k; l < kC; ++l) if(qua[i][j][k][l]){
					ll v = 1; if(i != j) v *= 2; if(k != l) v *= 2;
					mad(ans, v * qua[i][j][k][l] * qua[j][i][l][k] % MOD);
				}
 
	debug(ans);
	return ans;
}
 
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin >> n; cin.ignore();
	vector<vector<string>> bkt(11);
	string s;
	for(int i = 1; i <= n; ++i){
		getline(cin, s);
		bkt[s.length()].push_back(s);
	}
 
	int ans = 0;
	for(int i = 3; i <= 10; ++i)
		mad(ans, solve(bkt[i]));
	cout << ans;
	return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 65144 KB Output is correct
2 Correct 231 ms 65228 KB Output is correct
3 Correct 233 ms 65300 KB Output is correct
4 Correct 234 ms 65448 KB Output is correct
5 Correct 234 ms 65168 KB Output is correct
6 Correct 228 ms 65348 KB Output is correct
7 Correct 225 ms 65384 KB Output is correct
8 Correct 224 ms 65264 KB Output is correct
9 Correct 230 ms 65220 KB Output is correct
10 Correct 261 ms 65332 KB Output is correct
11 Correct 228 ms 65248 KB Output is correct
12 Correct 229 ms 65284 KB Output is correct
13 Correct 227 ms 65196 KB Output is correct
14 Correct 227 ms 65220 KB Output is correct
15 Correct 225 ms 65348 KB Output is correct
16 Correct 222 ms 65240 KB Output is correct
17 Correct 223 ms 65176 KB Output is correct
18 Correct 224 ms 65196 KB Output is correct
19 Correct 230 ms 65228 KB Output is correct
20 Correct 232 ms 65196 KB Output is correct
21 Correct 228 ms 65244 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 65144 KB Output is correct
2 Correct 231 ms 65228 KB Output is correct
3 Correct 233 ms 65300 KB Output is correct
4 Correct 234 ms 65448 KB Output is correct
5 Correct 234 ms 65168 KB Output is correct
6 Correct 228 ms 65348 KB Output is correct
7 Correct 225 ms 65384 KB Output is correct
8 Correct 224 ms 65264 KB Output is correct
9 Correct 230 ms 65220 KB Output is correct
10 Correct 261 ms 65332 KB Output is correct
11 Correct 228 ms 65248 KB Output is correct
12 Correct 229 ms 65284 KB Output is correct
13 Correct 227 ms 65196 KB Output is correct
14 Correct 227 ms 65220 KB Output is correct
15 Correct 225 ms 65348 KB Output is correct
16 Correct 222 ms 65240 KB Output is correct
17 Correct 223 ms 65176 KB Output is correct
18 Correct 224 ms 65196 KB Output is correct
19 Correct 230 ms 65228 KB Output is correct
20 Correct 232 ms 65196 KB Output is correct
21 Correct 228 ms 65244 KB Output is correct
22 Correct 241 ms 64516 KB Output is correct
23 Correct 239 ms 64408 KB Output is correct
24 Correct 243 ms 64380 KB Output is correct
25 Correct 237 ms 64560 KB Output is correct
26 Correct 238 ms 64456 KB Output is correct
27 Correct 241 ms 64360 KB Output is correct
28 Correct 241 ms 64392 KB Output is correct
29 Correct 235 ms 64428 KB Output is correct
30 Correct 240 ms 64408 KB Output is correct
31 Correct 238 ms 64348 KB Output is correct
32 Correct 238 ms 64352 KB Output is correct
33 Correct 236 ms 64456 KB Output is correct
34 Correct 235 ms 64404 KB Output is correct
35 Correct 240 ms 64408 KB Output is correct
36 Correct 242 ms 64428 KB Output is correct
37 Correct 237 ms 64476 KB Output is correct
38 Correct 246 ms 64464 KB Output is correct
39 Correct 246 ms 64420 KB Output is correct
40 Correct 242 ms 64340 KB Output is correct
41 Correct 235 ms 64352 KB Output is correct
42 Correct 235 ms 64532 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 65144 KB Output is correct
2 Correct 231 ms 65228 KB Output is correct
3 Correct 233 ms 65300 KB Output is correct
4 Correct 234 ms 65448 KB Output is correct
5 Correct 234 ms 65168 KB Output is correct
6 Correct 228 ms 65348 KB Output is correct
7 Correct 225 ms 65384 KB Output is correct
8 Correct 224 ms 65264 KB Output is correct
9 Correct 230 ms 65220 KB Output is correct
10 Correct 261 ms 65332 KB Output is correct
11 Correct 228 ms 65248 KB Output is correct
12 Correct 229 ms 65284 KB Output is correct
13 Correct 227 ms 65196 KB Output is correct
14 Correct 227 ms 65220 KB Output is correct
15 Correct 225 ms 65348 KB Output is correct
16 Correct 222 ms 65240 KB Output is correct
17 Correct 223 ms 65176 KB Output is correct
18 Correct 224 ms 65196 KB Output is correct
19 Correct 230 ms 65228 KB Output is correct
20 Correct 232 ms 65196 KB Output is correct
21 Correct 228 ms 65244 KB Output is correct
22 Correct 241 ms 64516 KB Output is correct
23 Correct 239 ms 64408 KB Output is correct
24 Correct 243 ms 64380 KB Output is correct
25 Correct 237 ms 64560 KB Output is correct
26 Correct 238 ms 64456 KB Output is correct
27 Correct 241 ms 64360 KB Output is correct
28 Correct 241 ms 64392 KB Output is correct
29 Correct 235 ms 64428 KB Output is correct
30 Correct 240 ms 64408 KB Output is correct
31 Correct 238 ms 64348 KB Output is correct
32 Correct 238 ms 64352 KB Output is correct
33 Correct 236 ms 64456 KB Output is correct
34 Correct 235 ms 64404 KB Output is correct
35 Correct 240 ms 64408 KB Output is correct
36 Correct 242 ms 64428 KB Output is correct
37 Correct 237 ms 64476 KB Output is correct
38 Correct 246 ms 64464 KB Output is correct
39 Correct 246 ms 64420 KB Output is correct
40 Correct 242 ms 64340 KB Output is correct
41 Correct 235 ms 64352 KB Output is correct
42 Correct 235 ms 64532 KB Output is correct
43 Correct 400 ms 64488 KB Output is correct
44 Correct 389 ms 64536 KB Output is correct
45 Correct 388 ms 64396 KB Output is correct
46 Correct 404 ms 64412 KB Output is correct
47 Correct 389 ms 64348 KB Output is correct
48 Correct 404 ms 64220 KB Output is correct
49 Correct 398 ms 64376 KB Output is correct
50 Correct 403 ms 64356 KB Output is correct
51 Correct 396 ms 64260 KB Output is correct
52 Correct 405 ms 64332 KB Output is correct
53 Correct 413 ms 64416 KB Output is correct
54 Correct 394 ms 64448 KB Output is correct
55 Correct 399 ms 64276 KB Output is correct
56 Correct 407 ms 64456 KB Output is correct
57 Correct 403 ms 64276 KB Output is correct
58 Correct 394 ms 64412 KB Output is correct
59 Correct 389 ms 64292 KB Output is correct
60 Correct 389 ms 64264 KB Output is correct
61 Correct 403 ms 64416 KB Output is correct
62 Correct 394 ms 64464 KB Output is correct
63 Correct 392 ms 64300 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 65144 KB Output is correct
2 Correct 231 ms 65228 KB Output is correct
3 Correct 233 ms 65300 KB Output is correct
4 Correct 234 ms 65448 KB Output is correct
5 Correct 234 ms 65168 KB Output is correct
6 Correct 228 ms 65348 KB Output is correct
7 Correct 225 ms 65384 KB Output is correct
8 Correct 224 ms 65264 KB Output is correct
9 Correct 230 ms 65220 KB Output is correct
10 Correct 261 ms 65332 KB Output is correct
11 Correct 228 ms 65248 KB Output is correct
12 Correct 229 ms 65284 KB Output is correct
13 Correct 227 ms 65196 KB Output is correct
14 Correct 227 ms 65220 KB Output is correct
15 Correct 225 ms 65348 KB Output is correct
16 Correct 222 ms 65240 KB Output is correct
17 Correct 223 ms 65176 KB Output is correct
18 Correct 224 ms 65196 KB Output is correct
19 Correct 230 ms 65228 KB Output is correct
20 Correct 232 ms 65196 KB Output is correct
21 Correct 228 ms 65244 KB Output is correct
22 Correct 241 ms 64516 KB Output is correct
23 Correct 239 ms 64408 KB Output is correct
24 Correct 243 ms 64380 KB Output is correct
25 Correct 237 ms 64560 KB Output is correct
26 Correct 238 ms 64456 KB Output is correct
27 Correct 241 ms 64360 KB Output is correct
28 Correct 241 ms 64392 KB Output is correct
29 Correct 235 ms 64428 KB Output is correct
30 Correct 240 ms 64408 KB Output is correct
31 Correct 238 ms 64348 KB Output is correct
32 Correct 238 ms 64352 KB Output is correct
33 Correct 236 ms 64456 KB Output is correct
34 Correct 235 ms 64404 KB Output is correct
35 Correct 240 ms 64408 KB Output is correct
36 Correct 242 ms 64428 KB Output is correct
37 Correct 237 ms 64476 KB Output is correct
38 Correct 246 ms 64464 KB Output is correct
39 Correct 246 ms 64420 KB Output is correct
40 Correct 242 ms 64340 KB Output is correct
41 Correct 235 ms 64352 KB Output is correct
42 Correct 235 ms 64532 KB Output is correct
43 Correct 400 ms 64488 KB Output is correct
44 Correct 389 ms 64536 KB Output is correct
45 Correct 388 ms 64396 KB Output is correct
46 Correct 404 ms 64412 KB Output is correct
47 Correct 389 ms 64348 KB Output is correct
48 Correct 404 ms 64220 KB Output is correct
49 Correct 398 ms 64376 KB Output is correct
50 Correct 403 ms 64356 KB Output is correct
51 Correct 396 ms 64260 KB Output is correct
52 Correct 405 ms 64332 KB Output is correct
53 Correct 413 ms 64416 KB Output is correct
54 Correct 394 ms 64448 KB Output is correct
55 Correct 399 ms 64276 KB Output is correct
56 Correct 407 ms 64456 KB Output is correct
57 Correct 403 ms 64276 KB Output is correct
58 Correct 394 ms 64412 KB Output is correct
59 Correct 389 ms 64292 KB Output is correct
60 Correct 389 ms 64264 KB Output is correct
61 Correct 403 ms 64416 KB Output is correct
62 Correct 394 ms 64464 KB Output is correct
63 Correct 392 ms 64300 KB Output is correct
64 Execution timed out 1192 ms 64276 KB Time limit exceeded
65 Halted 0 ms 0 KB -