QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302858#7940. Impossible NumberstarjenRE 0ms0kbC++171.7kb2024-01-11 14:17:192024-01-11 14:17:19

Judging History

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

  • [2024-01-11 14:17:19]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-01-11 14:17:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
int solve(int n,vector<int> a,vector<int> b)
{
    int ans=inf;
    for(int i=0;i<n;i++)a.push_back(a[i]);
    for(int i=0;i<n;i++)b.push_back(b[i]);
    for(int i=0;i<n;i++){
        vector<vector<int>> ve(n+1);
        for(int j=0;j<2*n;j++)ve[a[j]].push_back(j); 
        if(a==b)ans=min(ans,i*(n-1));
        vector<int> r(2*n+1),l(2*n);
        for(int i=1;i<2*n;i++){
            if(a[i]==b[i-1])l[i]=l[i-1]+1;
            else l[i]=0;
        }
        for(int i=2*n-1;i>=0;i--){
            if(a[i]==b[i])r[i]=r[i+1]+1;
            else r[i]=0;
        }
        // cout<<"i="<<i<<"\n";
        // for(auto it:a)cout<<it<<" ";;cout<<"\n";
        // for(auto it:b)cout<<it<<" ";;cout<<"\n";
        for(int R=n-1;R<2*n;R++)if(l[R]>0){
            int L=R-n+1;
            int q=min(R-1,L+r[L]);
            int p=R-l[R];
            if(p>q)continue;
            // cout<<"L="<<L<<" R="<<R<<" p="<<p<<" q="<<q<<"\n";
            auto it=upper_bound(ve[b[R]].begin(),ve[b[R]].end(),q);
            if(it==ve[b[R]].begin())continue;
            it--;
            if(*it<p)continue;
            assert(*it<R);
            ans=min(ans,i*(n-1)+(R-*it));
        }
        if(ans!=inf)break;
        int zz=a[0];
        for(int j=0;j+1<n*2;j++)a[j]=a[j+1];
        a.back()=zz;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    int ans=solve(n,a,b);
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    ans=min(ans,solve(n,a,b));
    if(ans==inf)cout<<-1;
    else cout<<ans<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

2 3
1 8 7 0 6 2
1 2 5 4 9 3

output:


result: