QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527964#7956. Walk SwappingJooDdaeWA 0ms3708kbC++201.1kb2024-08-23 00:30:422024-08-23 00:30:43

Judging History

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

  • [2024-08-23 00:30:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3708kb
  • [2024-08-23 00:30:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e9;

int n, a[6060], b[6060], r[6060], r2[6060];

int solve() {
    for(int i=1;i<=n;i++) a[n+i] = a[i], b[n+i] = b[i];
    r[n+n+1] = r2[n+n+1] = n+n;
    for(int i=n+n;i>=1;i--) r[i] = (a[i] == b[i] ? r[i+1] : i-1);
    for(int i=n+n;i>=1;i--) r2[i] = (a[i] == b[i-1] ? r2[i+1] : i-1);

    int re = INF;
    for(int i=1;i<=n;i++) {
        int L = i, R = i+n-1;

        int M = r[L];
        if(M >= R || (a[M+1] == b[R] && r2[M+2] >= R)) re = min(re, R-M-1);
        // cout << i << " " << re << "]\n";
    }

    return re;
}

int solve1() {
    int re = INF;
    for(int i=1;i<n;i++) {
        re = min(re, solve() + n*min(i-1, n-i));
        rotate(a+1, a+2, a+1+n);
    }
    rotate(a+1, a+2, a+1+n);
    return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];


    int ans = solve1();
    reverse(a+1, a+1+n), reverse(b+1, b+1+n);
    ans = min(ans, solve1());
    cout << (ans == INF ? -1 : ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

6
2 1 1 2 2 1
1 2 2 2 1 1

output:

7

result:

ok single line: '7'

Test #3:

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

input:

6
4 1 3 6 2 5
6 2 1 3 4 5

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3708kb

input:

6
4 1 3 6 2 5
6 2 5 3 4 1

output:

14

result:

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