QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710235#7956. Walk Swappingucup-team3646WA 3ms3880kbC++202.8kb2024-11-04 19:09:202024-11-04 19:09:22

Judging History

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

  • [2024-11-04 19:09:22]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3880kb
  • [2024-11-04 19:09:20]
  • 提交

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;
                // assert(pr==i);
                int d = (pr - i + N) % N;
                int r = nextval[pr][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 << " " << shift * (N - 1) + r - i << 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

input:

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

output:

13

result:

ok single line: '13'

Test #6:

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

input:

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

output:

12

result:

ok single line: '12'

Test #7:

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

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #8:

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

input:

5
4 3 5 2 1
1 3 5 4 2

output:

2

result:

ok single line: '2'

Test #9:

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

input:

5
4 3 5 2 1
1 4 3 5 2

output:

4

result:

ok single line: '4'

Test #10:

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

input:

5
1 1 1 2 1
2 1 1 1 1

output:

2

result:

ok single line: '2'

Test #11:

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

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #12:

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

input:

4
4 3 2 1
1 3 4 2

output:

2

result:

ok single line: '2'

Test #13:

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

input:

10
2 3 1 1 3 4 5 5 6 1
1 1 3 4 5 3 5 1 7 2

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

5
1 4 5 3 2
5 3 2 1 4

output:

8

result:

ok single line: '8'

Test #15:

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

input:

5
1 2 3 4 5
5 2 1 3 4

output:

3

result:

ok single line: '3'

Test #16:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

10
1 2 3 2 2 2 1 1 1 1
2 1 1 1 1 1 2 2 3 2

output:

41

result:

ok single line: '41'

Test #18:

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

input:

10
1 1 1 2 2 4 4 4 2 2
1 1 2 2 4 4 2 2 1 4

output:

12

result:

ok single line: '12'

Test #19:

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

input:

12
3 3 3 2 2 2 4 4 2 2 1 3
3 3 2 2 4 4 2 2 2 1 3 3

output:

13

result:

ok single line: '13'

Test #20:

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

input:

12
3 3 2 2 2 2 4 4 2 2 1 2
2 2 2 2 4 4 2 2 2 1 3 3

output:

19

result:

ok single line: '19'

Test #21:

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

input:

12
3 3 2 4 2 2 4 4 2 2 1 2
2 2 2 2 4 4 2 2 4 1 3 3

output:

-1

result:

ok single line: '-1'

Test #22:

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

input:

20
3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5
2 3 5 4 4 5 1 2 3 2 5 3 1 1 5 3 2 4 5 1

output:

49

result:

ok single line: '49'

Test #23:

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

input:

20
3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5
3 2 3 4 5 1 2 3 5 4 4 5 1 2 3 2 5 1 1 5

output:

158

result:

ok single line: '158'

Test #24:

score: 0
Accepted
time: 2ms
memory: 3852kb

input:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
99 1...

output:

109

result:

ok single line: '109'

Test #25:

score: 0
Accepted
time: 3ms
memory: 3880kb

input:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 ...

output:

89

result:

ok single line: '89'

Test #26:

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

input:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
51 5...

output:

4924

result:

ok single line: '4924'

Test #27:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
51 5...

output:

4905

result:

ok single line: '4905'

Test #28:

score: 0
Accepted
time: 2ms
memory: 3848kb

input:

100
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20
9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 1...

output:

3990

result:

ok single line: '3990'

Test #29:

score: -100
Wrong Answer
time: 2ms
memory: 3676kb

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...

output:

126

result:

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