QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412359#3168. Letter Wheelslittlecat#WA 101ms3876kbC++141.7kb2024-05-16 12:22:462024-05-16 12:22:48

Judging History

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

  • [2024-05-16 12:22:48]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:3876kb
  • [2024-05-16 12:22:46]
  • 提交

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=998244353;
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);
}
int solve(int x, int y)
{
    int u=min(x,y), v=max(x,y);
    return min(min(u+n-v,v),n-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])
        {
            int u=v1[0], v=v2.back();
            ans=min(ans,min(u,n-u)+min(v,n-v));
            ans=min(ans,min(u,n-u)+min(v-u,n-(v-u)));
            ans=min(ans,min(v-u,n-(v-u))+min(v,n-v));
        }
        if(v1.back()>=v2[0])
        {
            int u=v2[0], v=v1.back();
            ans=min(ans,min(u,n-u)+min(v,n-v));
            ans=min(ans,min(u,n-u)+min(v-u,n-(v-u)));
            ans=min(ans,min(v-u,n-(v-u))+min(v,n-v));
        }
    }
    cout<<(ans==2*mx?-1:ans)<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

ABC
ABC
ABC

output:

2

result:

ok single line: '2'

Test #2:

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

input:

ABBBAAAA
BBBCCCBB
CCCCAAAC

output:

3

result:

ok single line: '3'

Test #3:

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

input:

AABB
BBCC
ACAC

output:

-1

result:

ok single line: '-1'

Test #4:

score: -100
Wrong Answer
time: 101ms
memory: 3760kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

-1

result:

wrong answer 1st lines differ - expected: '0', found: '-1'