QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226840#3168. Letter WheelsSolitaryDream#WA 0ms3688kbC++171.5kb2023-10-26 17:07:562023-10-26 17:07:56

Judging History

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

  • [2023-10-26 17:07:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3688kb
  • [2023-10-26 17:07:56]
  • 提交

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'