oj.uz

Submission #1039502

# Submission time Handle Problem Language Result Execution time Memory
1039502 2024-07-31T01:43:23 Z Edu175 Cubeword (CEOI19_cubeword) C++17
84 / 100
 1100 ms 7556 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,isudgh=b;i<isudgh;i++)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto jhglkdfjg:v)cout<<jhglkdfjg<<" ";cout<<"\n";}
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef int ll;
typedef long long LL;
typedef pair<ll,ll> ii;
// #pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
const ll MOD=998244353,MAXA=62;

ll add(ll a, ll b){a+=b;if(a>=MOD)a-=MOD;return a;}
ll sub(ll a, ll b){a-=b;if(a<0)a+=MOD;return a;}
ll mul(LL a, LL b){return a*b%MOD;}
int fpow(int a, ll b){
	int r=1;
	while(b){if(b&1)r=mul(r,a); b>>=1; a=mul(a,a);}
	return r;
}

ll A; //alphabet
ll q[62][62];
string cv(ll mk, ll sz){
	string r="(";
	fore(i,0,sz){
		if(i)r.pb(',');
		r+=to_string(mk%A),mk/=A;
	}
	r.pb(')');
	return r;
}

ll solve(vector<string>&a){
	if(!SZ(a))return 0;
	// cout<<"solve "; imp(a);
	ll n=SZ(a);
	vector<char>c;
	fore(i,0,n)c.pb(a[i][0]),c.pb(a[i].back());
	sort(ALL(c));
	vector<char> ci;
	fore(i,0,SZ(c))if(!i||c[i]!=c[i-1])ci.pb(c[i]);
	c=ci;
	for(auto &s:a){
		auto change=[&](char &j){
			ll p=lower_bound(ALL(c),j)-c.begin();
			j=p;
		};
		change(s[0]); change(s.back());
	}
	// imp(a);
	A=SZ(c);
	set<string> st[A][A];
	for(auto s:a){
		st[int(s[0])][int(s.back())].insert(s);
		reverse(ALL(s));
		st[int(s[0])][int(s.back())].insert(s);
	}
	fore(i,0,A)fore(j,0,A)q[i][j]=SZ(st[i][j]);
	/*fore(i,0,A){
		imp(q[i]);
	}*/
	vector<ll>pot(5);
	pot[0]=1;
	fore(i,1,5)pot[i]=pot[i-1]*A;
	
	vector<ll>num(pot[3]);
	fore(mk,0,pot[3]){
		vector<ll>a(3);
		ll mki=mk;
		fore(i,0,3)a[i]=mki%A,mki/=A;
		fore(c,0,A){
			ll val=1;
			fore(j,0,3)val=mul(val,q[a[j]][c]);
			num[mk]=add(num[mk],val);
		}
		// cout<<mk<<" "<<cv(mk,3)<<": "<<num[mk]<<"\n";
	}
	ll ans=0;
	fore(mk,0,pot[4]){	
		vector<ll>a(4);
		ll mki=mk;
		fore(i,0,4)a[i]=mki%A,mki/=A;
		ll res=1,m=mk/A;
		fore(i,0,4){
			res=mul(res,num[m]);
			m=(m+(a[i]*pot[3]))/A;
		}
		ans=add(ans,res);
		// imp(a);
		// imp(num);
		// cout<<": "<<res<<"\n\n";
	}
	return ans;
	
}
const ll MAXV=11;
int main(){FIN;
	ll n; cin>>n;
	vector<string> b[MAXV];
	fore(i,0,n){
		string s;cin>>s;
		b[SZ(s)].pb(s);
	}
	ll res=0;
	fore(i,0,MAXV){
		res=add(res,solve(b[i]));
	}
	// res=solve(b[5]);
	cout<<res<<"\n";
	return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6644 KB Output is correct
2 Correct 58 ms 7516 KB Output is correct
3 Correct 54 ms 7372 KB Output is correct
4 Correct 51 ms 7372 KB Output is correct
5 Correct 52 ms 7508 KB Output is correct
6 Correct 53 ms 7396 KB Output is correct
7 Correct 48 ms 7556 KB Output is correct
8 Correct 51 ms 7516 KB Output is correct
9 Correct 62 ms 7496 KB Output is correct
10 Correct 53 ms 7356 KB Output is correct
11 Correct 50 ms 7408 KB Output is correct
12 Correct 61 ms 7388 KB Output is correct
13 Correct 61 ms 7484 KB Output is correct
14 Correct 54 ms 7464 KB Output is correct
15 Correct 62 ms 7464 KB Output is correct
16 Correct 51 ms 7512 KB Output is correct
17 Correct 54 ms 7356 KB Output is correct
18 Correct 52 ms 7428 KB Output is correct
19 Correct 53 ms 7480 KB Output is correct
20 Correct 53 ms 7376 KB Output is correct
21 Correct 52 ms 7520 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6644 KB Output is correct
2 Correct 58 ms 7516 KB Output is correct
3 Correct 54 ms 7372 KB Output is correct
4 Correct 51 ms 7372 KB Output is correct
5 Correct 52 ms 7508 KB Output is correct
6 Correct 53 ms 7396 KB Output is correct
7 Correct 48 ms 7556 KB Output is correct
8 Correct 51 ms 7516 KB Output is correct
9 Correct 62 ms 7496 KB Output is correct
10 Correct 53 ms 7356 KB Output is correct
11 Correct 50 ms 7408 KB Output is correct
12 Correct 61 ms 7388 KB Output is correct
13 Correct 61 ms 7484 KB Output is correct
14 Correct 54 ms 7464 KB Output is correct
15 Correct 62 ms 7464 KB Output is correct
16 Correct 51 ms 7512 KB Output is correct
17 Correct 54 ms 7356 KB Output is correct
18 Correct 52 ms 7428 KB Output is correct
19 Correct 53 ms 7480 KB Output is correct
20 Correct 53 ms 7376 KB Output is correct
21 Correct 52 ms 7520 KB Output is correct
22 Correct 62 ms 6620 KB Output is correct
23 Correct 61 ms 6564 KB Output is correct
24 Correct 61 ms 6620 KB Output is correct
25 Correct 61 ms 6568 KB Output is correct
26 Correct 62 ms 6576 KB Output is correct
27 Correct 60 ms 6616 KB Output is correct
28 Correct 62 ms 6560 KB Output is correct
29 Correct 61 ms 6652 KB Output is correct
30 Correct 66 ms 6644 KB Output is correct
31 Correct 61 ms 6564 KB Output is correct
32 Correct 57 ms 6632 KB Output is correct
33 Correct 61 ms 6616 KB Output is correct
34 Correct 61 ms 6556 KB Output is correct
35 Correct 62 ms 6568 KB Output is correct
36 Correct 65 ms 6624 KB Output is correct
37 Correct 77 ms 6888 KB Output is correct
38 Correct 61 ms 6636 KB Output is correct
39 Correct 62 ms 6588 KB Output is correct
40 Correct 61 ms 6632 KB Output is correct
41 Correct 63 ms 6520 KB Output is correct
42 Correct 62 ms 6680 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6644 KB Output is correct
2 Correct 58 ms 7516 KB Output is correct
3 Correct 54 ms 7372 KB Output is correct
4 Correct 51 ms 7372 KB Output is correct
5 Correct 52 ms 7508 KB Output is correct
6 Correct 53 ms 7396 KB Output is correct
7 Correct 48 ms 7556 KB Output is correct
8 Correct 51 ms 7516 KB Output is correct
9 Correct 62 ms 7496 KB Output is correct
10 Correct 53 ms 7356 KB Output is correct
11 Correct 50 ms 7408 KB Output is correct
12 Correct 61 ms 7388 KB Output is correct
13 Correct 61 ms 7484 KB Output is correct
14 Correct 54 ms 7464 KB Output is correct
15 Correct 62 ms 7464 KB Output is correct
16 Correct 51 ms 7512 KB Output is correct
17 Correct 54 ms 7356 KB Output is correct
18 Correct 52 ms 7428 KB Output is correct
19 Correct 53 ms 7480 KB Output is correct
20 Correct 53 ms 7376 KB Output is correct
21 Correct 52 ms 7520 KB Output is correct
22 Correct 62 ms 6620 KB Output is correct
23 Correct 61 ms 6564 KB Output is correct
24 Correct 61 ms 6620 KB Output is correct
25 Correct 61 ms 6568 KB Output is correct
26 Correct 62 ms 6576 KB Output is correct
27 Correct 60 ms 6616 KB Output is correct
28 Correct 62 ms 6560 KB Output is correct
29 Correct 61 ms 6652 KB Output is correct
30 Correct 66 ms 6644 KB Output is correct
31 Correct 61 ms 6564 KB Output is correct
32 Correct 57 ms 6632 KB Output is correct
33 Correct 61 ms 6616 KB Output is correct
34 Correct 61 ms 6556 KB Output is correct
35 Correct 62 ms 6568 KB Output is correct
36 Correct 65 ms 6624 KB Output is correct
37 Correct 77 ms 6888 KB Output is correct
38 Correct 61 ms 6636 KB Output is correct
39 Correct 62 ms 6588 KB Output is correct
40 Correct 61 ms 6632 KB Output is correct
41 Correct 63 ms 6520 KB Output is correct
42 Correct 62 ms 6680 KB Output is correct
43 Correct 294 ms 6620 KB Output is correct
44 Correct 295 ms 6568 KB Output is correct
45 Correct 288 ms 6544 KB Output is correct
46 Correct 301 ms 6696 KB Output is correct
47 Correct 298 ms 6568 KB Output is correct
48 Correct 282 ms 6380 KB Output is correct
49 Correct 299 ms 6372 KB Output is correct
50 Correct 283 ms 6460 KB Output is correct
51 Correct 309 ms 6360 KB Output is correct
52 Correct 445 ms 6700 KB Output is correct
53 Correct 301 ms 6472 KB Output is correct
54 Correct 286 ms 6628 KB Output is correct
55 Correct 293 ms 6444 KB Output is correct
56 Correct 295 ms 6572 KB Output is correct
57 Correct 270 ms 6488 KB Output is correct
58 Correct 292 ms 6440 KB Output is correct
59 Correct 304 ms 6452 KB Output is correct
60 Correct 299 ms 6496 KB Output is correct
61 Correct 284 ms 6828 KB Output is correct
62 Correct 278 ms 6376 KB Output is correct
63 Correct 314 ms 6372 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6644 KB Output is correct
2 Correct 58 ms 7516 KB Output is correct
3 Correct 54 ms 7372 KB Output is correct
4 Correct 51 ms 7372 KB Output is correct
5 Correct 52 ms 7508 KB Output is correct
6 Correct 53 ms 7396 KB Output is correct
7 Correct 48 ms 7556 KB Output is correct
8 Correct 51 ms 7516 KB Output is correct
9 Correct 62 ms 7496 KB Output is correct
10 Correct 53 ms 7356 KB Output is correct
11 Correct 50 ms 7408 KB Output is correct
12 Correct 61 ms 7388 KB Output is correct
13 Correct 61 ms 7484 KB Output is correct
14 Correct 54 ms 7464 KB Output is correct
15 Correct 62 ms 7464 KB Output is correct
16 Correct 51 ms 7512 KB Output is correct
17 Correct 54 ms 7356 KB Output is correct
18 Correct 52 ms 7428 KB Output is correct
19 Correct 53 ms 7480 KB Output is correct
20 Correct 53 ms 7376 KB Output is correct
21 Correct 52 ms 7520 KB Output is correct
22 Correct 62 ms 6620 KB Output is correct
23 Correct 61 ms 6564 KB Output is correct
24 Correct 61 ms 6620 KB Output is correct
25 Correct 61 ms 6568 KB Output is correct
26 Correct 62 ms 6576 KB Output is correct
27 Correct 60 ms 6616 KB Output is correct
28 Correct 62 ms 6560 KB Output is correct
29 Correct 61 ms 6652 KB Output is correct
30 Correct 66 ms 6644 KB Output is correct
31 Correct 61 ms 6564 KB Output is correct
32 Correct 57 ms 6632 KB Output is correct
33 Correct 61 ms 6616 KB Output is correct
34 Correct 61 ms 6556 KB Output is correct
35 Correct 62 ms 6568 KB Output is correct
36 Correct 65 ms 6624 KB Output is correct
37 Correct 77 ms 6888 KB Output is correct
38 Correct 61 ms 6636 KB Output is correct
39 Correct 62 ms 6588 KB Output is correct
40 Correct 61 ms 6632 KB Output is correct
41 Correct 63 ms 6520 KB Output is correct
42 Correct 62 ms 6680 KB Output is correct
43 Correct 294 ms 6620 KB Output is correct
44 Correct 295 ms 6568 KB Output is correct
45 Correct 288 ms 6544 KB Output is correct
46 Correct 301 ms 6696 KB Output is correct
47 Correct 298 ms 6568 KB Output is correct
48 Correct 282 ms 6380 KB Output is correct
49 Correct 299 ms 6372 KB Output is correct
50 Correct 283 ms 6460 KB Output is correct
51 Correct 309 ms 6360 KB Output is correct
52 Correct 445 ms 6700 KB Output is correct
53 Correct 301 ms 6472 KB Output is correct
54 Correct 286 ms 6628 KB Output is correct
55 Correct 293 ms 6444 KB Output is correct
56 Correct 295 ms 6572 KB Output is correct
57 Correct 270 ms 6488 KB Output is correct
58 Correct 292 ms 6440 KB Output is correct
59 Correct 304 ms 6452 KB Output is correct
60 Correct 299 ms 6496 KB Output is correct
61 Correct 284 ms 6828 KB Output is correct
62 Correct 278 ms 6376 KB Output is correct
63 Correct 314 ms 6372 KB Output is correct
64 Execution timed out 1134 ms 7316 KB Time limit exceeded
65 Halted 0 ms 0 KB -