QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760567#7956. Walk SwappingSanguineChameleonTL 268ms823624kbC++202.5kb2024-11-18 17:37:002024-11-18 17:37:01

Judging History

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

  • [2024-11-18 17:37:01]
  • 评测
  • 测评结果:TL
  • 用时:268ms
  • 内存:823624kb
  • [2024-11-18 17:37:00]
  • 提交

answer

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

void justDoIt();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    justDoIt();
    return 0;
}

const int INF = 1e9 + 20;
const long long BASE = 1e4 + 3;
const long long MOD = 5e6 + 7;

void calc(vector<long long>& a, vector<vector<long long>>& shifts) {
    int n = a.size();
    // shifts[i][j] is clockwise
    for (int i = 0; i < n; i++) {
        vector<long long> rem(n - 1);
        for (int j = 0; j < n - 1; j++) {
            rem[j] = a[(i + 1 + j) % n];
        }
        long long h = 0;
        for (int j = 0; j < n - 1; j++) {
            h = (h * BASE + rem[j]) % MOD;
        }
        long long pw = 1;
        for (int j = 0; j < n - 2; j++) {
            pw = pw * BASE % MOD;
        }
        for (int j = 0; j < n - 1; j++) {
            shifts[i][j] = h;
            h = (h + MOD - (pw * rem[j]) % MOD) % MOD;
            h = (h * BASE + rem[j]) % MOD;
        }
    }
}

int solve(vector<long long> a, vector<long long> b) {
    int n = a.size();
    if (n == 1) {
        if (a[0] == b[0]) {
            return 0;
        }
        else {
            return INF;
        }
    }
    vector<vector<long long>> shiftsA(n, vector<long long>(n - 1));
    vector<vector<long long>> shiftsB(n, vector<long long>(n - 1));
    calc(a, shiftsA);
    calc(b, shiftsB);
    vector<vector<long long>> f(n, vector<long long>(MOD, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n - 1; j++) {
            f[i][shiftsB[i][j]] = n - 1 - j;
        }
        f[i][shiftsB[i][0]] = 0;
    }
    int res = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int dist = (j + n - i) % n;
            long long h = shiftsA[i][dist % (n - 1)];
            int it = f[j][h];
            if (it != -1) {
                res = min(res, dist + it * n);
            }
        }
    }
    return res;
}

void justDoIt() {
    int n;
    cin >> n;
    vector<long long> 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 res = INF;
    for (int iter = 0; iter < 2; iter++) {
        res = min(res, solve(a, b));
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
    }
    if (res == INF) {
        cout << -1;
        return;
    }
    else {
        cout << res;
        return;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 55ms
memory: 198552kb

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 70ms
memory: 276776kb

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: 91ms
memory: 276728kb

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: 55ms
memory: 198516kb

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 75ms
memory: 276576kb

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: 59ms
memory: 276596kb

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: 60ms
memory: 198468kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 63ms
memory: 237480kb

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: 48ms
memory: 237464kb

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: 55ms
memory: 237688kb

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: 49ms
memory: 198572kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 56ms
memory: 198708kb

input:

4
4 3 2 1
1 3 4 2

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 118ms
memory: 432872kb

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: 60ms
memory: 237508kb

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: 65ms
memory: 237672kb

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: 111ms
memory: 432872kb

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: 135ms
memory: 432712kb

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: 116ms
memory: 432800kb

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: 150ms
memory: 511048kb

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: 136ms
memory: 511056kb

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: 175ms
memory: 511196kb

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: 236ms
memory: 823620kb

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: 268ms
memory: 823624kb

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: -100
Time Limit Exceeded

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:


result: