QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226840 | #3168. Letter Wheels | SolitaryDream# | WA | 0ms | 3688kb | C++17 | 1.5kb | 2023-10-26 17:07:56 | 2023-10-26 17:07:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
const ull bs=1313131,P=(1ull<<61)+1;
int n;
vector<vector<int> > v(3);
ull mul(const ull &a,const ull &b)
{
return (__int128)a*b%P;
}
int main()
{
ios::sync_with_stdio(false);
for(int i=0;i<3;i++)
{
string s;
cin>>s;
n=s.size();
for(int j=0;j<n;j++)
v[i].push_back(s[j]-'A');
}
int pw=1;
for(int i=1;i<n;i++)
pw=mul(pw,bs);
int ans=1e9;
for(int r=0;r<3;r++)
{
int x=(r==0?1:0);
int y=x^r^3;
unordered_map<ull,int>st;
ull h=0;
for(int i=0;i<n;i++)
h=(mul(h,bs)+v[y][i])%P;
for(int i=0;i<n;i++)
{
if(!st.count(h))
st[h]=min(i,n-i);
else
st[h]=min(st[h],min(i,n-i));
h=(mul((h-mul(pw,v[y][i])+P),bs)+v[y][i])%P;
}
for(int i=0;i<n;i++)
{
bool ok=1;
for(int j=0;j<n;j++)
if(v[r][j]==v[x][(i+j)%n])
ok=0;
if(!ok)
continue;
int e=min(i,n-i);
h=0;
for(int j=0;j<n;j++)
h=(mul(h,bs)+(6-v[x][(i+j)%n]-v[r][j])%3)%P;
if(st.count(h))
ans=min(ans,e+st[h]);
}
}
if(ans>n*10)
puts("-1");
else
printf("%d\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3688kb
input:
ABC ABC ABC
output:
2
result:
ok single line: '2'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3604kb
input:
ABBBAAAA BBBCCCBB CCCCAAAC
output:
-1
result:
wrong answer 1st lines differ - expected: '3', found: '-1'