QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234526#3168. Letter WheelsPhantomThreshold#AC ✓479ms4716kbC++202.5kb2023-11-01 18:48:542023-11-01 18:48:55

Judging History

你现在查看的是最新测评结果

  • [2023-11-01 18:48:55]
  • 评测
  • 测评结果:AC
  • 用时:479ms
  • 内存:4716kb
  • [2023-11-01 18:48:54]
  • 提交

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>mp; int mpn;
vector<int>V[maxn];

int calc(int a,int b,int c) //a=0
{
	if(b>c) swap(b,c);
	//0=a<b<c
	int ret= min(b,n-b)+min(c,n-c);
	{
		int u=n+a-b,v=c-b;
		ret=min( ret, min(u,n-u)+min(v,n-v) );
	}
	{
		int u=n+a-c,v=n+b-c;
		ret=min( ret, min(u,n-u)+min(v,n-v) );
	}
	return ret;
}

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(mp.count(temp)==0) mp[temp]=++mpn;
		V[mp[temp]].push_back(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<=0;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( mp.count(temp)!=0 )
		{
			int id=mp[temp];
			for(auto k:V[id])
			{
				ans=min(ans, calc(x,y,k) );
			}
		}
	}
	
	if(ans==inf) ans=-1;
	cout<<ans<<endl;
	
	return 0;
}

详细

Test #1:

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

input:

ABC
ABC
ABC

output:

2

result:

ok single line: '2'

Test #2:

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

input:

ABBBAAAA
BBBCCCBB
CCCCAAAC

output:

3

result:

ok single line: '3'

Test #3:

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

input:

AABB
BBCC
ACAC

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 479ms
memory: 4064kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 387ms
memory: 4480kb

input:

ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 381ms
memory: 4168kb

input:

ABBBCCACACBCBACCBBCCBACBBBABAABBCAACCABBBACABAACABBCAAACACABACAACACCBCABBABBCBBCCABBCCABCCACBCCCBABABAACAAACCCCBACCABBAACCAABCABBABAAABACBAABABCABAAACABAAACABBCBCACABACBBBBBBCCABBACAAAACBAAACABCABABBBABBAABACABABCCBCCBAAAABBCACACABBCABCAAAABABAAACBCCAAABCABBBAACBABBBACBBBCBCAABCCCCBBACCBABABBAAACAAB...

output:

911

result:

ok single line: '911'

Test #7:

score: 0
Accepted
time: 381ms
memory: 4368kb

input:

AACABBCACCCBABAACCBBACAAAACABCCCCCCAABBCACACBAACBBBCCBAABBCBAABCABBAABCABAACBBABBAAABBAACACBAACBBACAABCAACBCBCACBACAABCCBBACACCABCCCCCCCCACABBBCBCBBACACCBACCBCAACACAABABACCAACCCAABBBABCCCACBCBAACAACCCBAAABBCCCBBABBBBBABAACAACCABCAABCCABBAABCBACBAABBBACCBAABBCAAACACCCCCCCBBAAABBCBBCCACCAAACBABCCAABBB...

output:

465

result:

ok single line: '465'

Test #8:

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

input:

CBCBAABCCCABBACCBABCAABBCACBBBCABCCAABCCCABBCACAAAACACBCBCCCCBCBBCCCBACCAABABACCABCBCCBBCCAACABCCABBBBBABACCBCBABCACCCCCBBCBAABABBCACBCABBCAAAACBABCCACABABCBABABBCAABABCCAACABCBBBBCABCAAABCABCAACBBBBBCBBCAABCBACABACBBCAACBCBCCABBCABBACCBBABCBABBCCCBBCABABAACBBBACCCACBAAAACCCBACACAACBACABACCCCBACCCCA...

output:

861

result:

ok single line: '861'

Test #9:

score: 0
Accepted
time: 399ms
memory: 4428kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2612

result:

ok single line: '2612'

Test #10:

score: 0
Accepted
time: 402ms
memory: 4420kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2189

result:

ok single line: '2189'

Test #11:

score: 0
Accepted
time: 395ms
memory: 4480kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1519

result:

ok single line: '1519'

Test #12:

score: 0
Accepted
time: 405ms
memory: 4640kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2546

result:

ok single line: '2546'

Test #13:

score: 0
Accepted
time: 396ms
memory: 4480kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2319

result:

ok single line: '2319'

Test #14:

score: 0
Accepted
time: 395ms
memory: 4412kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2505

result:

ok single line: '2505'

Test #15:

score: 0
Accepted
time: 399ms
memory: 4716kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2474

result:

ok single line: '2474'

Test #16:

score: 0
Accepted
time: 399ms
memory: 4416kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2993

result:

ok single line: '2993'

Test #17:

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

input:

ACCCCBBB
BBBACCCC
BAAABAAA

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 3ms
memory: 3824kb

input:

CBBACBBAABAACCCBACCCBABAABBCABCABBACABBAAAAAACABCBCCACCABACBAAAAABBBABCCCBCBCACACACABBCBCACAAACCAABCCBCACABCBABBABBCBCCCACABCCBBCBCAACABBACCBCBCABABAAABACBBAAACACACBBACBBCACACACBCAAAABBCCBCBCCCBBBCBABCBBCACCCABBAACBACABAABBCABCBAACBCAABBBCACAAABAAABCBABACACBAAAABCAABACCABAAAACBCCBBCAAABABCABBAACCACC...

output:

183

result:

ok single line: '183'

Test #19:

score: 0
Accepted
time: 399ms
memory: 4660kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1332

result:

ok single line: '1332'