QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234519#3168. Letter WheelsPhantomThreshold#TL 591ms4984kbC++202.2kb2023-11-01 18:33:132023-11-01 18:33:14

Judging History

This is the latest submission verdict.

  • [2023-11-01 18:33:14]
  • Judged
  • Verdict: TL
  • Time: 591ms
  • Memory: 4984kb
  • [2023-11-01 18:33:13]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int inf  = 1e9;
const int maxn = 5050;
const int mod1 = 998244353;
const int mod2 = 1e9+7;
const int b1   = 11;
const int b2   = 13;

struct node
{
	int a,b;
	friend inline node operator +(const node &k1,const node &k2){ return (node){ (k1.a+k2.a)%mod1, (k1.b+k2.b)%mod2 }; }
	friend inline node operator -(const node &k1,const node &k2){ return (node){ (k1.a-k2.a+mod1)%mod1, (k1.b-k2.b+mod2)%mod2}; }
	friend inline node operator *(const node &k1,const node &k2){ return (node){ (ll)k1.a*k2.a%mod1, (ll)k1.b*k2.b%mod2 }; }
}ha[maxn],hb[maxn],hc[maxn],pw[maxn];

int n;
int A[maxn],B[maxn],C[maxn];
int ok[maxn];

map< pair<int,int>, int>mpn,mpx;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	string str;
	cin>>str; n=str.size(); str=' '+str;
	for(int i=1;i<=n;i++) A[i]=str[i]-'A'+1;
	cin>>str; n=str.size(); str=' '+str;
	for(int i=1;i<=n;i++) B[i]=str[i]-'A'+1;
	cin>>str; n=str.size(); str=' '+str;
	for(int i=1;i<=n;i++) C[i]=str[i]-'A'+1;
	
	pw[0]=(node){1,1};
	pw[1]=(node){b1,b2};
	for(int i=2;i<=n;i++) pw[i]=pw[i-1]*pw[1];
	
	for(int k=0;k<n;k++)
	{
		ok[k]=1;
		for(int i=1;i<=n;i++)
		{
			int j=i+k; if(j>n) j-=n;
			if(A[i]==B[j])
			{
				ok[k]=0;
				break;
			}
		}
	}
	
	for(int k=0;k<n;k++)
	{
		ha[k]=hb[k]=hc[k]=(node){0,0};
		for(int i=1;i<=n;i++)
		{
			int j=i+k; if(j>n) j-=n;
			
			ha[k]= ha[k]*pw[1]+(node){A[j],A[j]};
			hb[k]= hb[k]*pw[1]+(node){B[j],B[j]};
			hc[k]= hc[k]*pw[1]+(node){C[j],C[j]};
		}
		
		auto temp= make_pair(hc[k].a,hc[k].b);
		if( mpn.count(temp)==0 || mpn[temp]>k ) mpn[temp]=k;
		if( mpx.count(temp)==0 || mpx[temp]<k ) mpx[temp]=k;
	}
	
	node ful=(node){0,0};
	for(int i=1;i<=n;i++) ful= ful+ ( pw[i-1]*(node){6,6} );
	
	int ans=inf;
	for(int x=0;x<n;x++) for(int y=0;y<n;y++)
	{
		int delta= y>=x ? y-x : n-x+y;
		if(!ok[delta]) continue;
		
		node tc= ful-ha[x]-hb[y];
		auto temp= make_pair( tc.a, tc.b );
		if( mpn.count(temp)!=0 )
		{
			int use=min(x,n-x)+min(y,n-y)+min(mpn[temp],n-mpx[temp]);
			ans=min(ans,use);
		}
	}
	
	if(ans==inf) ans=-1;
	cout<<ans<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

ABC
ABC
ABC

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

ABBBAAAA
BBBCCCBB
CCCCAAAC

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

AABB
BBCC
ACAC

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 591ms
memory: 4132kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 561ms
memory: 4984kb

input:

ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 374ms
memory: 4276kb

input:

ABBBCCACACBCBACCBBCCBACBBBABAABBCAACCABBBACABAACABBCAAACACABACAACACCBCABBABBCBBCCABBCCABCCACBCCCBABABAACAAACCCCBACCABBAACCAABCABBABAAABACBAABABCABAAACABAAACABBCBCACABACBBBBBBCCABBACAAAACBAAACABCABABBBABBAABACABABCCBCCBAAAABBCACACABBCABCAAAABABAAACBCCAAABCABBBAACBABBBACBBBCBCAABCCCCBBACCBABABBAAACAAB...

output:

911

result:

ok single line: '911'

Test #7:

score: 0
Accepted
time: 383ms
memory: 4308kb

input:

AACABBCACCCBABAACCBBACAAAACABCCCCCCAABBCACACBAACBBBCCBAABBCBAABCABBAABCABAACBBABBAAABBAACACBAACBBACAABCAACBCBCACBACAABCCBBACACCABCCCCCCCCACABBBCBCBBACACCBACCBCAACACAABABACCAACCCAABBBABCCCACBCBAACAACCCBAAABBCCCBBABBBBBABAACAACCABCAABCCABBAABCBACBAABBBACCBAABBCAAACACCCCCCCBBAAABBCBBCCACCAAACBABCCAABBB...

output:

465

result:

ok single line: '465'

Test #8:

score: 0
Accepted
time: 374ms
memory: 4280kb

input:

CBCBAABCCCABBACCBABCAABBCACBBBCABCCAABCCCABBCACAAAACACBCBCCCCBCBBCCCBACCAABABACCABCBCCBBCCAACABCCABBBBBABACCBCBABCACCCCCBBCBAABABBCACBCABBCAAAACBABCCACABABCBABABBCAABABCCAACABCBBBBCABCAAABCABCAACBBBBBCBBCAABCBACABACBBCAACBCBCCABBCABBACCBBABCBABBCCCBBCABABAACBBBACCCACBAAAACCCBACACAACBACABACCCCBACCCCA...

output:

861

result:

ok single line: '861'

Test #9:

score: -100
Time Limit Exceeded

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:


result: