QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#412349 | #3168. Letter Wheels | littlecat# | WA | 107ms | 3672kb | C++14 | 1.7kb | 2024-05-16 12:17:23 | 2024-05-16 12:17:23 |
Judging History
answer
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define For(i,a,b) for(int i=(a); i<(b); i++)
using namespace std;
const int mx=5000; typedef long long ll; const ll mod=1000000007;
int n, a[3][mx], h[mx+1], p[mx+1];
unordered_map<ll,vector<int>> m, m2;
void ins(ll x, int i)
{
if(m.find(x)==m.end()) m[x]={};
m[x].push_back(i);
}
vector<int> qry(ll x)
{
if(m.find(x)==m.end()) return {};
return m[x];
}
int solve(int x, int y)
{
int u=min(x,y), v=max(x,y);
return min(min(u+n-v,v),v+v-u);
}
int main()
{
string s[3]; For(t,0,3) cin>>s[t]; n=s[0].size();
For(t,0,3) For(i,0,n) a[t][i]=s[t][i]-'A';
p[0]=1; For(i,0,n) h[i+1]=(h[i]*3+a[2][i])%mod, p[i+1]=(p[i]*3)%mod;
For(i,0,n) ins((h[n]*p[i]+h[i]*(1-p[n]))%mod,i);
int ans=2*mx;
For(i,0,n)
{
ll t=0; bool bad=0;
For(j,0,n)
{
if(a[0][j]==a[1][(i+j)%n]) {bad=1; break;}
t=(t*3+3-a[0][j]-a[1][(i+j)%n])%mod;
}
if(!bad) m2[t].push_back(i);
}
For(i,0,n)
{
ll H=(h[n]*p[i]+h[i]*(1-p[n]))%mod;
if(m.find(H)==m.end()||m2.find(H)==m2.end()) continue;
vector<int> v1=m[H], v2=m2[H];
sort(v1.begin(),v1.end()), sort(v2.begin(),v2.end());
if(v2.back()>=v1[0])
{
ans=min(ans,v1[0]+n-v2.back());
ans=min(ans,v2.back());
ans=min(ans,2*v2.back()-v1[0]);
}
if(v1.back()>=v2[0])
{
ans=min(ans,v2[0]+n-v1.back());
ans=min(ans,v1.back());
ans=min(ans,2*v1.back()-v2[0]);
}
}
cout<<(ans==2*mx?-1:ans)<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
ABC ABC ABC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
ABBBAAAA BBBCCCBB CCCCAAAC
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
AABB BBCC ACAC
output:
-1
result:
ok single line: '-1'
Test #4:
score: -100
Wrong Answer
time: 107ms
memory: 3672kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1
result:
wrong answer 1st lines differ - expected: '0', found: '-1'