oj.uz

Submission #1038339

# Submission time Handle Problem Language Result Execution time Memory
1038339 2024-07-29T17:04:43 Z vjudge1 Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 14288 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 long long ll;
typedef pair<ll,ll> ii;
const ll MOD=998244353;

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;}

ll A; //alphabet
vector<vector<ll>> q,g={
	{},
	{0},
	{0},
	{0},
	{1,2},
	{1,3},
	{2,3},
	{4,5,6}
};
vector<ll>bor={0,0,0,1,0,1,2,4},tam={1,2,3,3,4,4,3,0};
vector<ll>pot(6);

unordered_map<ll,ll> dp[8];

ll get(ll i, ll j, ll h){
	ll p=i-1-j;
	ll ret=h/pot[p]%A;
	// cout<<"get "<<i<<" "<<j<<" "<<h<<": "<<p<<": "<<ret<<"\n";
	return ret;
}
ll go(ll i, ll h, ll c){
	return (h*A+c)%pot[tam[i]];
}
ll f(ll i, ll h){
	if(i==8)return 1;
	if(dp[i].count(h))return dp[i][h];
	ll &res=dp[i][h];
	fore(c,0,A){// pongo c
		ll resi=1;
		for(auto j:g[i]){
			ll d=get(i,j,h);
			resi=mul(resi,q[c][d]);
		}
		// cout<<i<<""
		if(resi)res=add(res,mul(resi,f(i+1,go(i,h,c))));
	}
	// cout<<i<<" "<<h<<": "<<res<<"\n";
	return res;
}
ll solve(vector<string>&a){
	// cout<<"solve "; imp(a);
	ll n=SZ(a);
	vector<char>c;
	fore(i,0,n)for(auto j:a[i])c.pb(j);
	sort(ALL(c));
	vector<char> ci;
	fore(i,0,SZ(c))if(!i||c[i]!=c[i-1])ci.pb(c[i]);
	c=ci;
	fore(i,0,n){
		for(auto &j:a[i]){
			ll p=lower_bound(ALL(c),j)-c.begin();
			j=p;
		}
	}
	// imp(a);
	A=SZ(c);
	q=vector<vector<ll>>(A,vector<ll>(A));
	set<string> st[A][A];
	for(auto s:a){
		st[s[0]][s.back()].insert(s);
		reverse(ALL(s));
		st[s[0]][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]);
	}*/
	pot[0]=1;
	fore(i,1,6)pot[i]=pot[i-1]*A;
	fore(i,0,8)dp[i].clear();
	ll res=f(0,0);
	return res;
}
const ll MAXV=1e5+5;
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;
}

Compilation message

cubeword.cpp: In function 'll solve(std::vector<std::__cxx11::basic_string<char> >&)':
cubeword.cpp:81:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |   st[s[0]][s.back()].insert(s);
      |          ^
cubeword.cpp:81:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |   st[s[0]][s.back()].insert(s);
      |            ~~~~~~^~
cubeword.cpp:83:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |   st[s[0]][s.back()].insert(s);
      |          ^
cubeword.cpp:83:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |   st[s[0]][s.back()].insert(s);
      |            ~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 9204 KB Output is correct
2 Correct 140 ms 9320 KB Output is correct
3 Correct 150 ms 9308 KB Output is correct
4 Correct 144 ms 9300 KB Output is correct
5 Correct 146 ms 9364 KB Output is correct
6 Correct 143 ms 9172 KB Output is correct
7 Correct 147 ms 9252 KB Output is correct
8 Correct 147 ms 9384 KB Output is correct
9 Correct 143 ms 9296 KB Output is correct
10 Correct 145 ms 9360 KB Output is correct
11 Correct 167 ms 9204 KB Output is correct
12 Correct 145 ms 9364 KB Output is correct
13 Correct 142 ms 9216 KB Output is correct
14 Correct 147 ms 9516 KB Output is correct
15 Correct 139 ms 9392 KB Output is correct
16 Correct 144 ms 9296 KB Output is correct
17 Correct 143 ms 9356 KB Output is correct
18 Correct 150 ms 9208 KB Output is correct
19 Correct 143 ms 9280 KB Output is correct
20 Correct 136 ms 9168 KB Output is correct
21 Correct 143 ms 9300 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 9204 KB Output is correct
2 Correct 140 ms 9320 KB Output is correct
3 Correct 150 ms 9308 KB Output is correct
4 Correct 144 ms 9300 KB Output is correct
5 Correct 146 ms 9364 KB Output is correct
6 Correct 143 ms 9172 KB Output is correct
7 Correct 147 ms 9252 KB Output is correct
8 Correct 147 ms 9384 KB Output is correct
9 Correct 143 ms 9296 KB Output is correct
10 Correct 145 ms 9360 KB Output is correct
11 Correct 167 ms 9204 KB Output is correct
12 Correct 145 ms 9364 KB Output is correct
13 Correct 142 ms 9216 KB Output is correct
14 Correct 147 ms 9516 KB Output is correct
15 Correct 139 ms 9392 KB Output is correct
16 Correct 144 ms 9296 KB Output is correct
17 Correct 143 ms 9356 KB Output is correct
18 Correct 150 ms 9208 KB Output is correct
19 Correct 143 ms 9280 KB Output is correct
20 Correct 136 ms 9168 KB Output is correct
21 Correct 143 ms 9300 KB Output is correct
22 Execution timed out 1148 ms 14288 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 9204 KB Output is correct
2 Correct 140 ms 9320 KB Output is correct
3 Correct 150 ms 9308 KB Output is correct
4 Correct 144 ms 9300 KB Output is correct
5 Correct 146 ms 9364 KB Output is correct
6 Correct 143 ms 9172 KB Output is correct
7 Correct 147 ms 9252 KB Output is correct
8 Correct 147 ms 9384 KB Output is correct
9 Correct 143 ms 9296 KB Output is correct
10 Correct 145 ms 9360 KB Output is correct
11 Correct 167 ms 9204 KB Output is correct
12 Correct 145 ms 9364 KB Output is correct
13 Correct 142 ms 9216 KB Output is correct
14 Correct 147 ms 9516 KB Output is correct
15 Correct 139 ms 9392 KB Output is correct
16 Correct 144 ms 9296 KB Output is correct
17 Correct 143 ms 9356 KB Output is correct
18 Correct 150 ms 9208 KB Output is correct
19 Correct 143 ms 9280 KB Output is correct
20 Correct 136 ms 9168 KB Output is correct
21 Correct 143 ms 9300 KB Output is correct
22 Execution timed out 1148 ms 14288 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 9204 KB Output is correct
2 Correct 140 ms 9320 KB Output is correct
3 Correct 150 ms 9308 KB Output is correct
4 Correct 144 ms 9300 KB Output is correct
5 Correct 146 ms 9364 KB Output is correct
6 Correct 143 ms 9172 KB Output is correct
7 Correct 147 ms 9252 KB Output is correct
8 Correct 147 ms 9384 KB Output is correct
9 Correct 143 ms 9296 KB Output is correct
10 Correct 145 ms 9360 KB Output is correct
11 Correct 167 ms 9204 KB Output is correct
12 Correct 145 ms 9364 KB Output is correct
13 Correct 142 ms 9216 KB Output is correct
14 Correct 147 ms 9516 KB Output is correct
15 Correct 139 ms 9392 KB Output is correct
16 Correct 144 ms 9296 KB Output is correct
17 Correct 143 ms 9356 KB Output is correct
18 Correct 150 ms 9208 KB Output is correct
19 Correct 143 ms 9280 KB Output is correct
20 Correct 136 ms 9168 KB Output is correct
21 Correct 143 ms 9300 KB Output is correct
22 Execution timed out 1148 ms 14288 KB Time limit exceeded
23 Halted 0 ms 0 KB -