oj.uz

Submission #446993

# Submission time Handle Problem Language Result Execution time Memory
446993 2021-07-24T07:56:23 Z fhvirus Cubeword (CEOI19_cubeword) C++17
50 / 100
 153 ms 15628 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 = 26;
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 i = 0; i < kC; ++i)
		for(int j = 0; j < kC; ++j)
			for(int k = 0; k < kC; ++k)
				for(int u = 0; u < kC; ++u){
					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)
				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 139 ms 8292 KB Output is correct
2 Correct 143 ms 9200 KB Output is correct
3 Correct 141 ms 9244 KB Output is correct
4 Correct 145 ms 9200 KB Output is correct
5 Correct 146 ms 9184 KB Output is correct
6 Correct 143 ms 9244 KB Output is correct
7 Correct 153 ms 9152 KB Output is correct
8 Correct 148 ms 9244 KB Output is correct
9 Correct 150 ms 9148 KB Output is correct
10 Correct 142 ms 9136 KB Output is correct
11 Correct 141 ms 9100 KB Output is correct
12 Correct 147 ms 9168 KB Output is correct
13 Correct 144 ms 9200 KB Output is correct
14 Correct 143 ms 9188 KB Output is correct
15 Correct 145 ms 9216 KB Output is correct
16 Correct 150 ms 9156 KB Output is correct
17 Correct 142 ms 9212 KB Output is correct
18 Correct 144 ms 9192 KB Output is correct
19 Correct 144 ms 9164 KB Output is correct
20 Correct 150 ms 9240 KB Output is correct
21 Correct 143 ms 9172 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 8292 KB Output is correct
2 Correct 143 ms 9200 KB Output is correct
3 Correct 141 ms 9244 KB Output is correct
4 Correct 145 ms 9200 KB Output is correct
5 Correct 146 ms 9184 KB Output is correct
6 Correct 143 ms 9244 KB Output is correct
7 Correct 153 ms 9152 KB Output is correct
8 Correct 148 ms 9244 KB Output is correct
9 Correct 150 ms 9148 KB Output is correct
10 Correct 142 ms 9136 KB Output is correct
11 Correct 141 ms 9100 KB Output is correct
12 Correct 147 ms 9168 KB Output is correct
13 Correct 144 ms 9200 KB Output is correct
14 Correct 143 ms 9188 KB Output is correct
15 Correct 145 ms 9216 KB Output is correct
16 Correct 150 ms 9156 KB Output is correct
17 Correct 142 ms 9212 KB Output is correct
18 Correct 144 ms 9192 KB Output is correct
19 Correct 144 ms 9164 KB Output is correct
20 Correct 150 ms 9240 KB Output is correct
21 Correct 143 ms 9172 KB Output is correct
22 Correct 141 ms 8280 KB Output is correct
23 Correct 139 ms 8304 KB Output is correct
24 Correct 145 ms 8212 KB Output is correct
25 Correct 145 ms 8208 KB Output is correct
26 Correct 144 ms 8292 KB Output is correct
27 Correct 146 ms 8288 KB Output is correct
28 Correct 142 ms 8336 KB Output is correct
29 Correct 139 ms 8192 KB Output is correct
30 Correct 137 ms 8288 KB Output is correct
31 Correct 138 ms 8292 KB Output is correct
32 Correct 140 ms 8200 KB Output is correct
33 Correct 142 ms 8472 KB Output is correct
34 Correct 137 ms 8272 KB Output is correct
35 Correct 141 ms 8208 KB Output is correct
36 Correct 138 ms 8276 KB Output is correct
37 Correct 151 ms 8360 KB Output is correct
38 Correct 140 ms 8228 KB Output is correct
39 Correct 144 ms 8396 KB Output is correct
40 Correct 137 ms 8276 KB Output is correct
41 Correct 144 ms 8432 KB Output is correct
42 Correct 142 ms 8400 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 8292 KB Output is correct
2 Correct 143 ms 9200 KB Output is correct
3 Correct 141 ms 9244 KB Output is correct
4 Correct 145 ms 9200 KB Output is correct
5 Correct 146 ms 9184 KB Output is correct
6 Correct 143 ms 9244 KB Output is correct
7 Correct 153 ms 9152 KB Output is correct
8 Correct 148 ms 9244 KB Output is correct
9 Correct 150 ms 9148 KB Output is correct
10 Correct 142 ms 9136 KB Output is correct
11 Correct 141 ms 9100 KB Output is correct
12 Correct 147 ms 9168 KB Output is correct
13 Correct 144 ms 9200 KB Output is correct
14 Correct 143 ms 9188 KB Output is correct
15 Correct 145 ms 9216 KB Output is correct
16 Correct 150 ms 9156 KB Output is correct
17 Correct 142 ms 9212 KB Output is correct
18 Correct 144 ms 9192 KB Output is correct
19 Correct 144 ms 9164 KB Output is correct
20 Correct 150 ms 9240 KB Output is correct
21 Correct 143 ms 9172 KB Output is correct
22 Correct 141 ms 8280 KB Output is correct
23 Correct 139 ms 8304 KB Output is correct
24 Correct 145 ms 8212 KB Output is correct
25 Correct 145 ms 8208 KB Output is correct
26 Correct 144 ms 8292 KB Output is correct
27 Correct 146 ms 8288 KB Output is correct
28 Correct 142 ms 8336 KB Output is correct
29 Correct 139 ms 8192 KB Output is correct
30 Correct 137 ms 8288 KB Output is correct
31 Correct 138 ms 8292 KB Output is correct
32 Correct 140 ms 8200 KB Output is correct
33 Correct 142 ms 8472 KB Output is correct
34 Correct 137 ms 8272 KB Output is correct
35 Correct 141 ms 8208 KB Output is correct
36 Correct 138 ms 8276 KB Output is correct
37 Correct 151 ms 8360 KB Output is correct
38 Correct 140 ms 8228 KB Output is correct
39 Correct 144 ms 8396 KB Output is correct
40 Correct 137 ms 8276 KB Output is correct
41 Correct 144 ms 8432 KB Output is correct
42 Correct 142 ms 8400 KB Output is correct
43 Runtime error 151 ms 15628 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 8292 KB Output is correct
2 Correct 143 ms 9200 KB Output is correct
3 Correct 141 ms 9244 KB Output is correct
4 Correct 145 ms 9200 KB Output is correct
5 Correct 146 ms 9184 KB Output is correct
6 Correct 143 ms 9244 KB Output is correct
7 Correct 153 ms 9152 KB Output is correct
8 Correct 148 ms 9244 KB Output is correct
9 Correct 150 ms 9148 KB Output is correct
10 Correct 142 ms 9136 KB Output is correct
11 Correct 141 ms 9100 KB Output is correct
12 Correct 147 ms 9168 KB Output is correct
13 Correct 144 ms 9200 KB Output is correct
14 Correct 143 ms 9188 KB Output is correct
15 Correct 145 ms 9216 KB Output is correct
16 Correct 150 ms 9156 KB Output is correct
17 Correct 142 ms 9212 KB Output is correct
18 Correct 144 ms 9192 KB Output is correct
19 Correct 144 ms 9164 KB Output is correct
20 Correct 150 ms 9240 KB Output is correct
21 Correct 143 ms 9172 KB Output is correct
22 Correct 141 ms 8280 KB Output is correct
23 Correct 139 ms 8304 KB Output is correct
24 Correct 145 ms 8212 KB Output is correct
25 Correct 145 ms 8208 KB Output is correct
26 Correct 144 ms 8292 KB Output is correct
27 Correct 146 ms 8288 KB Output is correct
28 Correct 142 ms 8336 KB Output is correct
29 Correct 139 ms 8192 KB Output is correct
30 Correct 137 ms 8288 KB Output is correct
31 Correct 138 ms 8292 KB Output is correct
32 Correct 140 ms 8200 KB Output is correct
33 Correct 142 ms 8472 KB Output is correct
34 Correct 137 ms 8272 KB Output is correct
35 Correct 141 ms 8208 KB Output is correct
36 Correct 138 ms 8276 KB Output is correct
37 Correct 151 ms 8360 KB Output is correct
38 Correct 140 ms 8228 KB Output is correct
39 Correct 144 ms 8396 KB Output is correct
40 Correct 137 ms 8276 KB Output is correct
41 Correct 144 ms 8432 KB Output is correct
42 Correct 142 ms 8400 KB Output is correct
43 Runtime error 151 ms 15628 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -