QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234526 | #3168. Letter Wheels | PhantomThreshold# | AC ✓ | 479ms | 4716kb | C++20 | 2.5kb | 2023-11-01 18:48:54 | 2023-11-01 18:48:55 |
Judging History
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'