QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527954#7956. Walk SwappingJooDdaeWA 0ms3884kbC++201.1kb2024-08-23 00:16:142024-08-23 00:16:14

Judging History

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

  • [2024-08-23 00:16:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3884kb
  • [2024-08-23 00:16:14]
  • 提交

answer

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

const int INF = 1e9;

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

vector<int> find(int a[], int L, int R) {
    vector<int> re;
    for(int i=L;i<=R;i++) re.push_back(a[i]);
    return re;
}

int solve() {
    for(int i=1;i<=n;i++) a[n+i] = a[i], b[n+i] = b[i];
    r[n+n+1] = n+n;
    for(int i=n+n;i>=1;i--) r[i] = (a[i] == b[i] ? r[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(a[M+1] == b[R] && find(a, M+2, R) == find(b, M+1, R-1)) re = min(re, R-M-1);
    }

    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 = INF;
    for(int i=1;i<=n;i++) {
        ans = min(ans, solve() + n*min(i-1, n-i));
        rotate(a+1, a+2, a+1+n);
    }
    reverse(a+1, a+1+n), reverse(b+1, b+1+n);
    for(int i=1;i<=n;i++) {
        ans = min(ans, solve() + n*min(i-1, n-i));
        rotate(a+1, a+2, a+1+n);
    }
    cout << (ans == INF ? -1 : ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3852kb

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: 3644kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

4
1 2 3 4
4 2 1 3

output:

1

result:

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