oj.uz

Submission #447044

# Submission time Handle Problem Language Result Execution time Memory
447044 2021-07-24T09:48:39 Z fhvirus Cubeword (CEOI19_cubeword) C++17
84 / 100
 1100 ms 65368 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 = 0; j < kC; ++j) if(adj[u][j])
				for(int k = 0; k < kC; ++k) if(adj[u][k]){
					int v = 1ll * adj[i][u] * adj[j][u] * adj[k][u] % MOD;
					mad(tri[i][j][k], v);
				}
 
	// construct qua
	for(int i = 0; i < kC; ++i)
		for(int j = 0; j < kC; ++j)
			for(int k = 0; k < kC; ++k) if(tri[i][j][k])
				for(int l = 0; 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);
				}
 
	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 241 ms 65260 KB Output is correct
2 Correct 237 ms 65236 KB Output is correct
3 Correct 236 ms 65292 KB Output is correct
4 Correct 237 ms 65204 KB Output is correct
5 Correct 239 ms 65260 KB Output is correct
6 Correct 246 ms 65328 KB Output is correct
7 Correct 235 ms 65180 KB Output is correct
8 Correct 238 ms 65240 KB Output is correct
9 Correct 237 ms 65236 KB Output is correct
10 Correct 237 ms 65244 KB Output is correct
11 Correct 233 ms 65156 KB Output is correct
12 Correct 242 ms 65188 KB Output is correct
13 Correct 232 ms 65268 KB Output is correct
14 Correct 289 ms 65300 KB Output is correct
15 Correct 236 ms 65280 KB Output is correct
16 Correct 240 ms 65228 KB Output is correct
17 Correct 238 ms 65200 KB Output is correct
18 Correct 240 ms 65240 KB Output is correct
19 Correct 271 ms 65248 KB Output is correct
20 Correct 240 ms 65236 KB Output is correct
21 Correct 237 ms 65368 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 65260 KB Output is correct
2 Correct 237 ms 65236 KB Output is correct
3 Correct 236 ms 65292 KB Output is correct
4 Correct 237 ms 65204 KB Output is correct
5 Correct 239 ms 65260 KB Output is correct
6 Correct 246 ms 65328 KB Output is correct
7 Correct 235 ms 65180 KB Output is correct
8 Correct 238 ms 65240 KB Output is correct
9 Correct 237 ms 65236 KB Output is correct
10 Correct 237 ms 65244 KB Output is correct
11 Correct 233 ms 65156 KB Output is correct
12 Correct 242 ms 65188 KB Output is correct
13 Correct 232 ms 65268 KB Output is correct
14 Correct 289 ms 65300 KB Output is correct
15 Correct 236 ms 65280 KB Output is correct
16 Correct 240 ms 65228 KB Output is correct
17 Correct 238 ms 65200 KB Output is correct
18 Correct 240 ms 65240 KB Output is correct
19 Correct 271 ms 65248 KB Output is correct
20 Correct 240 ms 65236 KB Output is correct
21 Correct 237 ms 65368 KB Output is correct
22 Correct 241 ms 64348 KB Output is correct
23 Correct 244 ms 64460 KB Output is correct
24 Correct 284 ms 64360 KB Output is correct
25 Correct 240 ms 64400 KB Output is correct
26 Correct 239 ms 64432 KB Output is correct
27 Correct 281 ms 64352 KB Output is correct
28 Correct 253 ms 64452 KB Output is correct
29 Correct 256 ms 64412 KB Output is correct
30 Correct 247 ms 64364 KB Output is correct
31 Correct 243 ms 64324 KB Output is correct
32 Correct 247 ms 64400 KB Output is correct
33 Correct 245 ms 64488 KB Output is correct
34 Correct 243 ms 64376 KB Output is correct
35 Correct 251 ms 64464 KB Output is correct
36 Correct 249 ms 64448 KB Output is correct
37 Correct 238 ms 64452 KB Output is correct
38 Correct 254 ms 64500 KB Output is correct
39 Correct 250 ms 64416 KB Output is correct
40 Correct 239 ms 64360 KB Output is correct
41 Correct 249 ms 64556 KB Output is correct
42 Correct 242 ms 64444 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 65260 KB Output is correct
2 Correct 237 ms 65236 KB Output is correct
3 Correct 236 ms 65292 KB Output is correct
4 Correct 237 ms 65204 KB Output is correct
5 Correct 239 ms 65260 KB Output is correct
6 Correct 246 ms 65328 KB Output is correct
7 Correct 235 ms 65180 KB Output is correct
8 Correct 238 ms 65240 KB Output is correct
9 Correct 237 ms 65236 KB Output is correct
10 Correct 237 ms 65244 KB Output is correct
11 Correct 233 ms 65156 KB Output is correct
12 Correct 242 ms 65188 KB Output is correct
13 Correct 232 ms 65268 KB Output is correct
14 Correct 289 ms 65300 KB Output is correct
15 Correct 236 ms 65280 KB Output is correct
16 Correct 240 ms 65228 KB Output is correct
17 Correct 238 ms 65200 KB Output is correct
18 Correct 240 ms 65240 KB Output is correct
19 Correct 271 ms 65248 KB Output is correct
20 Correct 240 ms 65236 KB Output is correct
21 Correct 237 ms 65368 KB Output is correct
22 Correct 241 ms 64348 KB Output is correct
23 Correct 244 ms 64460 KB Output is correct
24 Correct 284 ms 64360 KB Output is correct
25 Correct 240 ms 64400 KB Output is correct
26 Correct 239 ms 64432 KB Output is correct
27 Correct 281 ms 64352 KB Output is correct
28 Correct 253 ms 64452 KB Output is correct
29 Correct 256 ms 64412 KB Output is correct
30 Correct 247 ms 64364 KB Output is correct
31 Correct 243 ms 64324 KB Output is correct
32 Correct 247 ms 64400 KB Output is correct
33 Correct 245 ms 64488 KB Output is correct
34 Correct 243 ms 64376 KB Output is correct
35 Correct 251 ms 64464 KB Output is correct
36 Correct 249 ms 64448 KB Output is correct
37 Correct 238 ms 64452 KB Output is correct
38 Correct 254 ms 64500 KB Output is correct
39 Correct 250 ms 64416 KB Output is correct
40 Correct 239 ms 64360 KB Output is correct
41 Correct 249 ms 64556 KB Output is correct
42 Correct 242 ms 64444 KB Output is correct
43 Correct 348 ms 64448 KB Output is correct
44 Correct 352 ms 65188 KB Output is correct
45 Correct 339 ms 65084 KB Output is correct
46 Correct 343 ms 65128 KB Output is correct
47 Correct 335 ms 64988 KB Output is correct
48 Correct 341 ms 65060 KB Output is correct
49 Correct 337 ms 64956 KB Output is correct
50 Correct 342 ms 65088 KB Output is correct
51 Correct 339 ms 64960 KB Output is correct
52 Correct 337 ms 65104 KB Output is correct
53 Correct 345 ms 65016 KB Output is correct
54 Correct 338 ms 65308 KB Output is correct
55 Correct 340 ms 65004 KB Output is correct
56 Correct 333 ms 65312 KB Output is correct
57 Correct 340 ms 65160 KB Output is correct
58 Correct 338 ms 65000 KB Output is correct
59 Correct 338 ms 65080 KB Output is correct
60 Correct 338 ms 65000 KB Output is correct
61 Correct 338 ms 65008 KB Output is correct
62 Correct 333 ms 64908 KB Output is correct
63 Correct 341 ms 64984 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 65260 KB Output is correct
2 Correct 237 ms 65236 KB Output is correct
3 Correct 236 ms 65292 KB Output is correct
4 Correct 237 ms 65204 KB Output is correct
5 Correct 239 ms 65260 KB Output is correct
6 Correct 246 ms 65328 KB Output is correct
7 Correct 235 ms 65180 KB Output is correct
8 Correct 238 ms 65240 KB Output is correct
9 Correct 237 ms 65236 KB Output is correct
10 Correct 237 ms 65244 KB Output is correct
11 Correct 233 ms 65156 KB Output is correct
12 Correct 242 ms 65188 KB Output is correct
13 Correct 232 ms 65268 KB Output is correct
14 Correct 289 ms 65300 KB Output is correct
15 Correct 236 ms 65280 KB Output is correct
16 Correct 240 ms 65228 KB Output is correct
17 Correct 238 ms 65200 KB Output is correct
18 Correct 240 ms 65240 KB Output is correct
19 Correct 271 ms 65248 KB Output is correct
20 Correct 240 ms 65236 KB Output is correct
21 Correct 237 ms 65368 KB Output is correct
22 Correct 241 ms 64348 KB Output is correct
23 Correct 244 ms 64460 KB Output is correct
24 Correct 284 ms 64360 KB Output is correct
25 Correct 240 ms 64400 KB Output is correct
26 Correct 239 ms 64432 KB Output is correct
27 Correct 281 ms 64352 KB Output is correct
28 Correct 253 ms 64452 KB Output is correct
29 Correct 256 ms 64412 KB Output is correct
30 Correct 247 ms 64364 KB Output is correct
31 Correct 243 ms 64324 KB Output is correct
32 Correct 247 ms 64400 KB Output is correct
33 Correct 245 ms 64488 KB Output is correct
34 Correct 243 ms 64376 KB Output is correct
35 Correct 251 ms 64464 KB Output is correct
36 Correct 249 ms 64448 KB Output is correct
37 Correct 238 ms 64452 KB Output is correct
38 Correct 254 ms 64500 KB Output is correct
39 Correct 250 ms 64416 KB Output is correct
40 Correct 239 ms 64360 KB Output is correct
41 Correct 249 ms 64556 KB Output is correct
42 Correct 242 ms 64444 KB Output is correct
43 Correct 348 ms 64448 KB Output is correct
44 Correct 352 ms 65188 KB Output is correct
45 Correct 339 ms 65084 KB Output is correct
46 Correct 343 ms 65128 KB Output is correct
47 Correct 335 ms 64988 KB Output is correct
48 Correct 341 ms 65060 KB Output is correct
49 Correct 337 ms 64956 KB Output is correct
50 Correct 342 ms 65088 KB Output is correct
51 Correct 339 ms 64960 KB Output is correct
52 Correct 337 ms 65104 KB Output is correct
53 Correct 345 ms 65016 KB Output is correct
54 Correct 338 ms 65308 KB Output is correct
55 Correct 340 ms 65004 KB Output is correct
56 Correct 333 ms 65312 KB Output is correct
57 Correct 340 ms 65160 KB Output is correct
58 Correct 338 ms 65000 KB Output is correct
59 Correct 338 ms 65080 KB Output is correct
60 Correct 338 ms 65000 KB Output is correct
61 Correct 338 ms 65008 KB Output is correct
62 Correct 333 ms 64908 KB Output is correct
63 Correct 341 ms 64984 KB Output is correct
64 Execution timed out 1179 ms 64984 KB Time limit exceeded
65 Halted 0 ms 0 KB -