QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710292#7956. Walk Swappingucup-team3646WA 0ms3856kbC++202.8kb2024-11-04 19:20:082024-11-04 19:20:10

Judging History

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

  • [2024-11-04 19:20:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-11-04 19:20:08]
  • 提交

answer

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

bool deb = 0;
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i]--;
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
        B[i]--;
    }
    int an = 1e9 + 10;
    for (int tu = 0; tu < 2; tu++) {
        vector<vector<int>> nextval(N);
        vector<int> pos(N, -1);
        for (int i = 2 * N - 1; i >= 0; i--) {
            pos[B[i % N]] = i % N;
            if (i < N)nextval[i] = pos;
        }
        for (int shift = 0; shift < N; shift++) {
            int res = 1e9 + 10;
            vector<int> SA(N);
            for (int i = 0; i < N; i++)SA[i] = A[(i + shift) % N];
            vector<int> DB(N, 0);

            vector<vector<int>> sum(2 * N + 1, vector<int>(4, 0));
            vector<vector<int>> prevbit(N);

            for (int i = 0; i < N; i++) {
                if (SA[i] == B[i])DB[i]++;
                if (SA[i] == B[(i + N - 1) % N])DB[i] += 2;
            }
            if (deb)for (int i = 0; i < N; i++)cout << SA[i] << " \n"[i == N - 1];
            if (deb)for (int i = 0; i < N; i++)cout << DB[i] << " \n"[i == N - 1];
            vector<int> posbit(4, -1);
            for (int i = 0; i <= 2 * N; i++) {
                posbit[DB[i % N]] = i % N;
                if (i >= N)prevbit[i % N] = posbit;
            }


            for (int i = 0; i < N * 2; i++) {
                for (int j = 0; j < 4; j++)sum[i + 1][j] = sum[i][j];
                sum[i + 1][DB[i % N]]++;
            }
            if (sum[2 * N][0] > 2) {
                continue;
            }

            for (int i = 0; i < N; i++) {
                if (sum[2 * N][0] == 2 && DB[i] != 0)continue;

                int pr = prevbit[i][2];
                if (pr == -1)pr = i;
                int d = (pr - i + N) % N;
                int r = nextval[(pr-1+N)%N][SA[i]];

                d += (r - pr + N) % N;
                if (d >= N)continue;
                if (r < i)r += N;

                if (sum[r + 1][2] + sum[r + 1][3] - sum[i + 1][2] - sum[i + 1][3] != r - i)continue;
                int cost = shift * (N - 1) + r - i;
                r %= N;
                int l = i;
                if (l < r)l += N;
                if (sum[l][0] + sum[l][2] - sum[r + 1][2] - sum[r + 1][0] != 0)continue;
                if (deb)cout << shift << ":" << i << " " << r << " " << cost << endl;
                an = min(an, cost);
            }
        }
        reverse(A.begin(), A.end());
        reverse(B.begin(), B.end());
        if (deb)cout << "return" << endl;
    }
    cout << (an < 1e9 ? an : -1) << endl;
}

詳細信息

Test #1:

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

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

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

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

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

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

input:

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

output:

13

result:

ok single line: '13'

Test #6:

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

input:

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

output:

13

result:

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