oj.uz

Submission #447003

# Submission time Handle Problem Language Result Execution time Memory
447003 2021-07-24T08:10:14 Z fhvirus Cubeword (CEOI19_cubeword) C++17
84 / 100
 1100 ms 65564 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]){
					ll v = adj[i][u] * adj[j][u] * adj[k][u];
					mad(tri[i][j][k], (v % MOD));
				}
 
	// 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])
					mad(qua[i][j][k][l], 1ll * tri[i][j][k] * tri[j][k][l] % MOD);
 
	int ans = 0;
	for(int i = 0; i < kC; ++i)
		for(int j = 0; j < kC; ++j)
			for(int k = 0; k < kC; ++k)
				for(int l = 0; l < kC; ++l) if(qua[i][j][k][l])
					mad(ans, 1ll * 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 352 ms 65508 KB Output is correct
2 Correct 352 ms 65468 KB Output is correct
3 Correct 346 ms 65548 KB Output is correct
4 Correct 403 ms 65556 KB Output is correct
5 Correct 396 ms 65516 KB Output is correct
6 Correct 351 ms 65388 KB Output is correct
7 Correct 370 ms 65436 KB Output is correct
8 Correct 349 ms 65464 KB Output is correct
9 Correct 376 ms 65476 KB Output is correct
10 Correct 356 ms 65524 KB Output is correct
11 Correct 355 ms 65524 KB Output is correct
12 Correct 361 ms 65424 KB Output is correct
13 Correct 366 ms 65524 KB Output is correct
14 Correct 345 ms 65544 KB Output is correct
15 Correct 341 ms 65564 KB Output is correct
16 Correct 334 ms 65524 KB Output is correct
17 Correct 418 ms 65432 KB Output is correct
18 Correct 339 ms 65492 KB Output is correct
19 Correct 468 ms 65508 KB Output is correct
20 Correct 335 ms 65472 KB Output is correct
21 Correct 473 ms 65496 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 65508 KB Output is correct
2 Correct 352 ms 65468 KB Output is correct
3 Correct 346 ms 65548 KB Output is correct
4 Correct 403 ms 65556 KB Output is correct
5 Correct 396 ms 65516 KB Output is correct
6 Correct 351 ms 65388 KB Output is correct
7 Correct 370 ms 65436 KB Output is correct
8 Correct 349 ms 65464 KB Output is correct
9 Correct 376 ms 65476 KB Output is correct
10 Correct 356 ms 65524 KB Output is correct
11 Correct 355 ms 65524 KB Output is correct
12 Correct 361 ms 65424 KB Output is correct
13 Correct 366 ms 65524 KB Output is correct
14 Correct 345 ms 65544 KB Output is correct
15 Correct 341 ms 65564 KB Output is correct
16 Correct 334 ms 65524 KB Output is correct
17 Correct 418 ms 65432 KB Output is correct
18 Correct 339 ms 65492 KB Output is correct
19 Correct 468 ms 65508 KB Output is correct
20 Correct 335 ms 65472 KB Output is correct
21 Correct 473 ms 65496 KB Output is correct
22 Correct 349 ms 64712 KB Output is correct
23 Correct 346 ms 64784 KB Output is correct
24 Correct 371 ms 64596 KB Output is correct
25 Correct 390 ms 64720 KB Output is correct
26 Correct 353 ms 64660 KB Output is correct
27 Correct 354 ms 64748 KB Output is correct
28 Correct 348 ms 64688 KB Output is correct
29 Correct 377 ms 64760 KB Output is correct
30 Correct 336 ms 64692 KB Output is correct
31 Correct 342 ms 64704 KB Output is correct
32 Correct 337 ms 64652 KB Output is correct
33 Correct 355 ms 64664 KB Output is correct
34 Correct 343 ms 64648 KB Output is correct
35 Correct 373 ms 64740 KB Output is correct
36 Correct 341 ms 64824 KB Output is correct
37 Correct 371 ms 64660 KB Output is correct
38 Correct 343 ms 64732 KB Output is correct
39 Correct 341 ms 64596 KB Output is correct
40 Correct 347 ms 64700 KB Output is correct
41 Correct 355 ms 64624 KB Output is correct
42 Correct 492 ms 64664 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 65508 KB Output is correct
2 Correct 352 ms 65468 KB Output is correct
3 Correct 346 ms 65548 KB Output is correct
4 Correct 403 ms 65556 KB Output is correct
5 Correct 396 ms 65516 KB Output is correct
6 Correct 351 ms 65388 KB Output is correct
7 Correct 370 ms 65436 KB Output is correct
8 Correct 349 ms 65464 KB Output is correct
9 Correct 376 ms 65476 KB Output is correct
10 Correct 356 ms 65524 KB Output is correct
11 Correct 355 ms 65524 KB Output is correct
12 Correct 361 ms 65424 KB Output is correct
13 Correct 366 ms 65524 KB Output is correct
14 Correct 345 ms 65544 KB Output is correct
15 Correct 341 ms 65564 KB Output is correct
16 Correct 334 ms 65524 KB Output is correct
17 Correct 418 ms 65432 KB Output is correct
18 Correct 339 ms 65492 KB Output is correct
19 Correct 468 ms 65508 KB Output is correct
20 Correct 335 ms 65472 KB Output is correct
21 Correct 473 ms 65496 KB Output is correct
22 Correct 349 ms 64712 KB Output is correct
23 Correct 346 ms 64784 KB Output is correct
24 Correct 371 ms 64596 KB Output is correct
25 Correct 390 ms 64720 KB Output is correct
26 Correct 353 ms 64660 KB Output is correct
27 Correct 354 ms 64748 KB Output is correct
28 Correct 348 ms 64688 KB Output is correct
29 Correct 377 ms 64760 KB Output is correct
30 Correct 336 ms 64692 KB Output is correct
31 Correct 342 ms 64704 KB Output is correct
32 Correct 337 ms 64652 KB Output is correct
33 Correct 355 ms 64664 KB Output is correct
34 Correct 343 ms 64648 KB Output is correct
35 Correct 373 ms 64740 KB Output is correct
36 Correct 341 ms 64824 KB Output is correct
37 Correct 371 ms 64660 KB Output is correct
38 Correct 343 ms 64732 KB Output is correct
39 Correct 341 ms 64596 KB Output is correct
40 Correct 347 ms 64700 KB Output is correct
41 Correct 355 ms 64624 KB Output is correct
42 Correct 492 ms 64664 KB Output is correct
43 Correct 507 ms 64624 KB Output is correct
44 Correct 461 ms 64708 KB Output is correct
45 Correct 482 ms 64688 KB Output is correct
46 Correct 544 ms 64644 KB Output is correct
47 Correct 467 ms 64624 KB Output is correct
48 Correct 458 ms 64476 KB Output is correct
49 Correct 471 ms 64492 KB Output is correct
50 Correct 467 ms 64544 KB Output is correct
51 Correct 449 ms 64560 KB Output is correct
52 Correct 477 ms 64688 KB Output is correct
53 Correct 498 ms 64636 KB Output is correct
54 Correct 466 ms 64672 KB Output is correct
55 Correct 464 ms 64604 KB Output is correct
56 Correct 461 ms 64632 KB Output is correct
57 Correct 453 ms 64428 KB Output is correct
58 Correct 484 ms 64432 KB Output is correct
59 Correct 498 ms 64504 KB Output is correct
60 Correct 480 ms 64464 KB Output is correct
61 Correct 472 ms 64652 KB Output is correct
62 Correct 543 ms 64612 KB Output is correct
63 Correct 475 ms 64580 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 65508 KB Output is correct
2 Correct 352 ms 65468 KB Output is correct
3 Correct 346 ms 65548 KB Output is correct
4 Correct 403 ms 65556 KB Output is correct
5 Correct 396 ms 65516 KB Output is correct
6 Correct 351 ms 65388 KB Output is correct
7 Correct 370 ms 65436 KB Output is correct
8 Correct 349 ms 65464 KB Output is correct
9 Correct 376 ms 65476 KB Output is correct
10 Correct 356 ms 65524 KB Output is correct
11 Correct 355 ms 65524 KB Output is correct
12 Correct 361 ms 65424 KB Output is correct
13 Correct 366 ms 65524 KB Output is correct
14 Correct 345 ms 65544 KB Output is correct
15 Correct 341 ms 65564 KB Output is correct
16 Correct 334 ms 65524 KB Output is correct
17 Correct 418 ms 65432 KB Output is correct
18 Correct 339 ms 65492 KB Output is correct
19 Correct 468 ms 65508 KB Output is correct
20 Correct 335 ms 65472 KB Output is correct
21 Correct 473 ms 65496 KB Output is correct
22 Correct 349 ms 64712 KB Output is correct
23 Correct 346 ms 64784 KB Output is correct
24 Correct 371 ms 64596 KB Output is correct
25 Correct 390 ms 64720 KB Output is correct
26 Correct 353 ms 64660 KB Output is correct
27 Correct 354 ms 64748 KB Output is correct
28 Correct 348 ms 64688 KB Output is correct
29 Correct 377 ms 64760 KB Output is correct
30 Correct 336 ms 64692 KB Output is correct
31 Correct 342 ms 64704 KB Output is correct
32 Correct 337 ms 64652 KB Output is correct
33 Correct 355 ms 64664 KB Output is correct
34 Correct 343 ms 64648 KB Output is correct
35 Correct 373 ms 64740 KB Output is correct
36 Correct 341 ms 64824 KB Output is correct
37 Correct 371 ms 64660 KB Output is correct
38 Correct 343 ms 64732 KB Output is correct
39 Correct 341 ms 64596 KB Output is correct
40 Correct 347 ms 64700 KB Output is correct
41 Correct 355 ms 64624 KB Output is correct
42 Correct 492 ms 64664 KB Output is correct
43 Correct 507 ms 64624 KB Output is correct
44 Correct 461 ms 64708 KB Output is correct
45 Correct 482 ms 64688 KB Output is correct
46 Correct 544 ms 64644 KB Output is correct
47 Correct 467 ms 64624 KB Output is correct
48 Correct 458 ms 64476 KB Output is correct
49 Correct 471 ms 64492 KB Output is correct
50 Correct 467 ms 64544 KB Output is correct
51 Correct 449 ms 64560 KB Output is correct
52 Correct 477 ms 64688 KB Output is correct
53 Correct 498 ms 64636 KB Output is correct
54 Correct 466 ms 64672 KB Output is correct
55 Correct 464 ms 64604 KB Output is correct
56 Correct 461 ms 64632 KB Output is correct
57 Correct 453 ms 64428 KB Output is correct
58 Correct 484 ms 64432 KB Output is correct
59 Correct 498 ms 64504 KB Output is correct
60 Correct 480 ms 64464 KB Output is correct
61 Correct 472 ms 64652 KB Output is correct
62 Correct 543 ms 64612 KB Output is correct
63 Correct 475 ms 64580 KB Output is correct
64 Execution timed out 1180 ms 64464 KB Time limit exceeded
65 Halted 0 ms 0 KB -