oj.uz

Submission #446997

# Submission time Handle Problem Language Result Execution time Memory
446997 2021-07-24T08:02:45 Z fhvirus Cubeword (CEOI19_cubeword) C++17
84 / 100
 1100 ms 65440 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];
		debug(a, b);
		if(isPalim(i)) continue;
		reverse(AI(i));
		ss.insert(i);
		++adj[b][a];
		debug(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) if(adj[i][j])
			for(int k = 0; k < kC; ++k) if(tri[i][j][k])
				for(int l = 0; l < kC; ++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)
					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;
	vector<vector<string>> bkt(11);
	for(int i = 1; i <= n; ++i){
		string s; 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 619 ms 65440 KB Output is correct
2 Correct 631 ms 65244 KB Output is correct
3 Correct 620 ms 65308 KB Output is correct
4 Correct 607 ms 65256 KB Output is correct
5 Correct 612 ms 65360 KB Output is correct
6 Correct 610 ms 65248 KB Output is correct
7 Correct 619 ms 65268 KB Output is correct
8 Correct 618 ms 65244 KB Output is correct
9 Correct 622 ms 65220 KB Output is correct
10 Correct 608 ms 65200 KB Output is correct
11 Correct 616 ms 65248 KB Output is correct
12 Correct 617 ms 65200 KB Output is correct
13 Correct 652 ms 65268 KB Output is correct
14 Correct 619 ms 65336 KB Output is correct
15 Correct 624 ms 65308 KB Output is correct
16 Correct 616 ms 65320 KB Output is correct
17 Correct 629 ms 65412 KB Output is correct
18 Correct 620 ms 65148 KB Output is correct
19 Correct 622 ms 65332 KB Output is correct
20 Correct 613 ms 65280 KB Output is correct
21 Correct 621 ms 65364 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 65440 KB Output is correct
2 Correct 631 ms 65244 KB Output is correct
3 Correct 620 ms 65308 KB Output is correct
4 Correct 607 ms 65256 KB Output is correct
5 Correct 612 ms 65360 KB Output is correct
6 Correct 610 ms 65248 KB Output is correct
7 Correct 619 ms 65268 KB Output is correct
8 Correct 618 ms 65244 KB Output is correct
9 Correct 622 ms 65220 KB Output is correct
10 Correct 608 ms 65200 KB Output is correct
11 Correct 616 ms 65248 KB Output is correct
12 Correct 617 ms 65200 KB Output is correct
13 Correct 652 ms 65268 KB Output is correct
14 Correct 619 ms 65336 KB Output is correct
15 Correct 624 ms 65308 KB Output is correct
16 Correct 616 ms 65320 KB Output is correct
17 Correct 629 ms 65412 KB Output is correct
18 Correct 620 ms 65148 KB Output is correct
19 Correct 622 ms 65332 KB Output is correct
20 Correct 613 ms 65280 KB Output is correct
21 Correct 621 ms 65364 KB Output is correct
22 Correct 633 ms 64560 KB Output is correct
23 Correct 638 ms 64452 KB Output is correct
24 Correct 688 ms 64440 KB Output is correct
25 Correct 798 ms 64436 KB Output is correct
26 Correct 697 ms 64560 KB Output is correct
27 Correct 766 ms 64480 KB Output is correct
28 Correct 735 ms 64400 KB Output is correct
29 Correct 808 ms 64452 KB Output is correct
30 Correct 666 ms 64564 KB Output is correct
31 Correct 629 ms 64384 KB Output is correct
32 Correct 663 ms 64400 KB Output is correct
33 Correct 642 ms 64480 KB Output is correct
34 Correct 638 ms 64440 KB Output is correct
35 Correct 640 ms 64468 KB Output is correct
36 Correct 644 ms 64444 KB Output is correct
37 Correct 674 ms 64572 KB Output is correct
38 Correct 657 ms 64464 KB Output is correct
39 Correct 628 ms 64452 KB Output is correct
40 Correct 643 ms 64412 KB Output is correct
41 Correct 641 ms 64448 KB Output is correct
42 Correct 648 ms 64516 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 65440 KB Output is correct
2 Correct 631 ms 65244 KB Output is correct
3 Correct 620 ms 65308 KB Output is correct
4 Correct 607 ms 65256 KB Output is correct
5 Correct 612 ms 65360 KB Output is correct
6 Correct 610 ms 65248 KB Output is correct
7 Correct 619 ms 65268 KB Output is correct
8 Correct 618 ms 65244 KB Output is correct
9 Correct 622 ms 65220 KB Output is correct
10 Correct 608 ms 65200 KB Output is correct
11 Correct 616 ms 65248 KB Output is correct
12 Correct 617 ms 65200 KB Output is correct
13 Correct 652 ms 65268 KB Output is correct
14 Correct 619 ms 65336 KB Output is correct
15 Correct 624 ms 65308 KB Output is correct
16 Correct 616 ms 65320 KB Output is correct
17 Correct 629 ms 65412 KB Output is correct
18 Correct 620 ms 65148 KB Output is correct
19 Correct 622 ms 65332 KB Output is correct
20 Correct 613 ms 65280 KB Output is correct
21 Correct 621 ms 65364 KB Output is correct
22 Correct 633 ms 64560 KB Output is correct
23 Correct 638 ms 64452 KB Output is correct
24 Correct 688 ms 64440 KB Output is correct
25 Correct 798 ms 64436 KB Output is correct
26 Correct 697 ms 64560 KB Output is correct
27 Correct 766 ms 64480 KB Output is correct
28 Correct 735 ms 64400 KB Output is correct
29 Correct 808 ms 64452 KB Output is correct
30 Correct 666 ms 64564 KB Output is correct
31 Correct 629 ms 64384 KB Output is correct
32 Correct 663 ms 64400 KB Output is correct
33 Correct 642 ms 64480 KB Output is correct
34 Correct 638 ms 64440 KB Output is correct
35 Correct 640 ms 64468 KB Output is correct
36 Correct 644 ms 64444 KB Output is correct
37 Correct 674 ms 64572 KB Output is correct
38 Correct 657 ms 64464 KB Output is correct
39 Correct 628 ms 64452 KB Output is correct
40 Correct 643 ms 64412 KB Output is correct
41 Correct 641 ms 64448 KB Output is correct
42 Correct 648 ms 64516 KB Output is correct
43 Correct 750 ms 64376 KB Output is correct
44 Correct 743 ms 64456 KB Output is correct
45 Correct 782 ms 64260 KB Output is correct
46 Correct 729 ms 64416 KB Output is correct
47 Correct 723 ms 64260 KB Output is correct
48 Correct 722 ms 64296 KB Output is correct
49 Correct 750 ms 64260 KB Output is correct
50 Correct 747 ms 64220 KB Output is correct
51 Correct 713 ms 64268 KB Output is correct
52 Correct 715 ms 64536 KB Output is correct
53 Correct 715 ms 64480 KB Output is correct
54 Correct 735 ms 64448 KB Output is correct
55 Correct 715 ms 64256 KB Output is correct
56 Correct 710 ms 64592 KB Output is correct
57 Correct 704 ms 64272 KB Output is correct
58 Correct 717 ms 64316 KB Output is correct
59 Correct 722 ms 64260 KB Output is correct
60 Correct 721 ms 64368 KB Output is correct
61 Correct 715 ms 64312 KB Output is correct
62 Correct 720 ms 64316 KB Output is correct
63 Correct 727 ms 64344 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 65440 KB Output is correct
2 Correct 631 ms 65244 KB Output is correct
3 Correct 620 ms 65308 KB Output is correct
4 Correct 607 ms 65256 KB Output is correct
5 Correct 612 ms 65360 KB Output is correct
6 Correct 610 ms 65248 KB Output is correct
7 Correct 619 ms 65268 KB Output is correct
8 Correct 618 ms 65244 KB Output is correct
9 Correct 622 ms 65220 KB Output is correct
10 Correct 608 ms 65200 KB Output is correct
11 Correct 616 ms 65248 KB Output is correct
12 Correct 617 ms 65200 KB Output is correct
13 Correct 652 ms 65268 KB Output is correct
14 Correct 619 ms 65336 KB Output is correct
15 Correct 624 ms 65308 KB Output is correct
16 Correct 616 ms 65320 KB Output is correct
17 Correct 629 ms 65412 KB Output is correct
18 Correct 620 ms 65148 KB Output is correct
19 Correct 622 ms 65332 KB Output is correct
20 Correct 613 ms 65280 KB Output is correct
21 Correct 621 ms 65364 KB Output is correct
22 Correct 633 ms 64560 KB Output is correct
23 Correct 638 ms 64452 KB Output is correct
24 Correct 688 ms 64440 KB Output is correct
25 Correct 798 ms 64436 KB Output is correct
26 Correct 697 ms 64560 KB Output is correct
27 Correct 766 ms 64480 KB Output is correct
28 Correct 735 ms 64400 KB Output is correct
29 Correct 808 ms 64452 KB Output is correct
30 Correct 666 ms 64564 KB Output is correct
31 Correct 629 ms 64384 KB Output is correct
32 Correct 663 ms 64400 KB Output is correct
33 Correct 642 ms 64480 KB Output is correct
34 Correct 638 ms 64440 KB Output is correct
35 Correct 640 ms 64468 KB Output is correct
36 Correct 644 ms 64444 KB Output is correct
37 Correct 674 ms 64572 KB Output is correct
38 Correct 657 ms 64464 KB Output is correct
39 Correct 628 ms 64452 KB Output is correct
40 Correct 643 ms 64412 KB Output is correct
41 Correct 641 ms 64448 KB Output is correct
42 Correct 648 ms 64516 KB Output is correct
43 Correct 750 ms 64376 KB Output is correct
44 Correct 743 ms 64456 KB Output is correct
45 Correct 782 ms 64260 KB Output is correct
46 Correct 729 ms 64416 KB Output is correct
47 Correct 723 ms 64260 KB Output is correct
48 Correct 722 ms 64296 KB Output is correct
49 Correct 750 ms 64260 KB Output is correct
50 Correct 747 ms 64220 KB Output is correct
51 Correct 713 ms 64268 KB Output is correct
52 Correct 715 ms 64536 KB Output is correct
53 Correct 715 ms 64480 KB Output is correct
54 Correct 735 ms 64448 KB Output is correct
55 Correct 715 ms 64256 KB Output is correct
56 Correct 710 ms 64592 KB Output is correct
57 Correct 704 ms 64272 KB Output is correct
58 Correct 717 ms 64316 KB Output is correct
59 Correct 722 ms 64260 KB Output is correct
60 Correct 721 ms 64368 KB Output is correct
61 Correct 715 ms 64312 KB Output is correct
62 Correct 720 ms 64316 KB Output is correct
63 Correct 727 ms 64344 KB Output is correct
64 Execution timed out 1191 ms 64212 KB Time limit exceeded
65 Halted 0 ms 0 KB -