oj.uz

답안 #1038433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038433 2024-07-29T19:22:20 Z vjudge1 Cubeword (CEOI19_cubeword) C++17
50 / 100
 1100 ms 159480 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;}

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

vector<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]];
}
vector<ii>vis;
ll f(ll i, ll h){
	if(i==8)return 1;
	ll &res=dp[i][h];
	if(res!=-1)return res;
	res=0;
	vis.pb({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)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);
	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;
	ll res=f(0,0);
	for(auto [i,j]:vis)dp[i][j]=-1;
	vis.clear();
	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);
	}
	vector<ll>POT={1};
	fore(i,0,5)POT.pb(POT.back()*MAXA);
	fore(i,0,8){
		dp[i]=vector<ll>(POT[(i?tam[i-1]:0)],-1);
		// cout<<i<<": "<<SZ(dp[i])<<"\n";
	}
	// imp(POT); cout<<endl;
	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:88:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |   st[s[0]][s.back()].insert(s);
      |          ^
cubeword.cpp:88:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |   st[s[0]][s.back()].insert(s);
      |            ~~~~~~^~
cubeword.cpp:90:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |   st[s[0]][s.back()].insert(s);
      |          ^
cubeword.cpp:90:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |   st[s[0]][s.back()].insert(s);
      |            ~~~~~~^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 128248 KB Output is correct
2 Correct 98 ms 128420 KB Output is correct
3 Correct 98 ms 128336 KB Output is correct
4 Correct 99 ms 128356 KB Output is correct
5 Correct 94 ms 128344 KB Output is correct
6 Correct 97 ms 128320 KB Output is correct
7 Correct 100 ms 128296 KB Output is correct
8 Correct 104 ms 128352 KB Output is correct
9 Correct 96 ms 128264 KB Output is correct
10 Correct 95 ms 128452 KB Output is correct
11 Correct 97 ms 128244 KB Output is correct
12 Correct 95 ms 128304 KB Output is correct
13 Correct 102 ms 128256 KB Output is correct
14 Correct 98 ms 128436 KB Output is correct
15 Correct 95 ms 128296 KB Output is correct
16 Correct 98 ms 128356 KB Output is correct
17 Correct 93 ms 128276 KB Output is correct
18 Correct 97 ms 128416 KB Output is correct
19 Correct 104 ms 128212 KB Output is correct
20 Correct 96 ms 128200 KB Output is correct
21 Correct 93 ms 128340 KB Output is correct

Subtask #2
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 128248 KB Output is correct
2 Correct 98 ms 128420 KB Output is correct
3 Correct 98 ms 128336 KB Output is correct
4 Correct 99 ms 128356 KB Output is correct
5 Correct 94 ms 128344 KB Output is correct
6 Correct 97 ms 128320 KB Output is correct
7 Correct 100 ms 128296 KB Output is correct
8 Correct 104 ms 128352 KB Output is correct
9 Correct 96 ms 128264 KB Output is correct
10 Correct 95 ms 128452 KB Output is correct
11 Correct 97 ms 128244 KB Output is correct
12 Correct 95 ms 128304 KB Output is correct
13 Correct 102 ms 128256 KB Output is correct
14 Correct 98 ms 128436 KB Output is correct
15 Correct 95 ms 128296 KB Output is correct
16 Correct 98 ms 128356 KB Output is correct
17 Correct 93 ms 128276 KB Output is correct
18 Correct 97 ms 128416 KB Output is correct
19 Correct 104 ms 128212 KB Output is correct
20 Correct 96 ms 128200 KB Output is correct
21 Correct 93 ms 128340 KB Output is correct
22 Correct 379 ms 128452 KB Output is correct
23 Correct 333 ms 128360 KB Output is correct
24 Correct 375 ms 128476 KB Output is correct
25 Correct 331 ms 128340 KB Output is correct
26 Correct 354 ms 128644 KB Output is correct
27 Correct 369 ms 128492 KB Output is correct
28 Correct 364 ms 128788 KB Output is correct
29 Correct 380 ms 128568 KB Output is correct
30 Correct 351 ms 128696 KB Output is correct
31 Correct 331 ms 128536 KB Output is correct
32 Correct 371 ms 128724 KB Output is correct
33 Correct 367 ms 128520 KB Output is correct
34 Correct 352 ms 128408 KB Output is correct
35 Correct 348 ms 128444 KB Output is correct
36 Correct 329 ms 128344 KB Output is correct
37 Correct 321 ms 128352 KB Output is correct
38 Correct 343 ms 128424 KB Output is correct
39 Correct 345 ms 128480 KB Output is correct
40 Correct 327 ms 128352 KB Output is correct
41 Correct 337 ms 128548 KB Output is correct
42 Correct 314 ms 128528 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 128248 KB Output is correct
2 Correct 98 ms 128420 KB Output is correct
3 Correct 98 ms 128336 KB Output is correct
4 Correct 99 ms 128356 KB Output is correct
5 Correct 94 ms 128344 KB Output is correct
6 Correct 97 ms 128320 KB Output is correct
7 Correct 100 ms 128296 KB Output is correct
8 Correct 104 ms 128352 KB Output is correct
9 Correct 96 ms 128264 KB Output is correct
10 Correct 95 ms 128452 KB Output is correct
11 Correct 97 ms 128244 KB Output is correct
12 Correct 95 ms 128304 KB Output is correct
13 Correct 102 ms 128256 KB Output is correct
14 Correct 98 ms 128436 KB Output is correct
15 Correct 95 ms 128296 KB Output is correct
16 Correct 98 ms 128356 KB Output is correct
17 Correct 93 ms 128276 KB Output is correct
18 Correct 97 ms 128416 KB Output is correct
19 Correct 104 ms 128212 KB Output is correct
20 Correct 96 ms 128200 KB Output is correct
21 Correct 93 ms 128340 KB Output is correct
22 Correct 379 ms 128452 KB Output is correct
23 Correct 333 ms 128360 KB Output is correct
24 Correct 375 ms 128476 KB Output is correct
25 Correct 331 ms 128340 KB Output is correct
26 Correct 354 ms 128644 KB Output is correct
27 Correct 369 ms 128492 KB Output is correct
28 Correct 364 ms 128788 KB Output is correct
29 Correct 380 ms 128568 KB Output is correct
30 Correct 351 ms 128696 KB Output is correct
31 Correct 331 ms 128536 KB Output is correct
32 Correct 371 ms 128724 KB Output is correct
33 Correct 367 ms 128520 KB Output is correct
34 Correct 352 ms 128408 KB Output is correct
35 Correct 348 ms 128444 KB Output is correct
36 Correct 329 ms 128344 KB Output is correct
37 Correct 321 ms 128352 KB Output is correct
38 Correct 343 ms 128424 KB Output is correct
39 Correct 345 ms 128480 KB Output is correct
40 Correct 327 ms 128352 KB Output is correct
41 Correct 337 ms 128548 KB Output is correct
42 Correct 314 ms 128528 KB Output is correct
43 Execution timed out 1178 ms 159480 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 128248 KB Output is correct
2 Correct 98 ms 128420 KB Output is correct
3 Correct 98 ms 128336 KB Output is correct
4 Correct 99 ms 128356 KB Output is correct
5 Correct 94 ms 128344 KB Output is correct
6 Correct 97 ms 128320 KB Output is correct
7 Correct 100 ms 128296 KB Output is correct
8 Correct 104 ms 128352 KB Output is correct
9 Correct 96 ms 128264 KB Output is correct
10 Correct 95 ms 128452 KB Output is correct
11 Correct 97 ms 128244 KB Output is correct
12 Correct 95 ms 128304 KB Output is correct
13 Correct 102 ms 128256 KB Output is correct
14 Correct 98 ms 128436 KB Output is correct
15 Correct 95 ms 128296 KB Output is correct
16 Correct 98 ms 128356 KB Output is correct
17 Correct 93 ms 128276 KB Output is correct
18 Correct 97 ms 128416 KB Output is correct
19 Correct 104 ms 128212 KB Output is correct
20 Correct 96 ms 128200 KB Output is correct
21 Correct 93 ms 128340 KB Output is correct
22 Correct 379 ms 128452 KB Output is correct
23 Correct 333 ms 128360 KB Output is correct
24 Correct 375 ms 128476 KB Output is correct
25 Correct 331 ms 128340 KB Output is correct
26 Correct 354 ms 128644 KB Output is correct
27 Correct 369 ms 128492 KB Output is correct
28 Correct 364 ms 128788 KB Output is correct
29 Correct 380 ms 128568 KB Output is correct
30 Correct 351 ms 128696 KB Output is correct
31 Correct 331 ms 128536 KB Output is correct
32 Correct 371 ms 128724 KB Output is correct
33 Correct 367 ms 128520 KB Output is correct
34 Correct 352 ms 128408 KB Output is correct
35 Correct 348 ms 128444 KB Output is correct
36 Correct 329 ms 128344 KB Output is correct
37 Correct 321 ms 128352 KB Output is correct
38 Correct 343 ms 128424 KB Output is correct
39 Correct 345 ms 128480 KB Output is correct
40 Correct 327 ms 128352 KB Output is correct
41 Correct 337 ms 128548 KB Output is correct
42 Correct 314 ms 128528 KB Output is correct
43 Execution timed out 1178 ms 159480 KB Time limit exceeded
44 Halted 0 ms 0 KB -