QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760555#7956. Walk SwappingSanguineChameleon#TL 503ms1643924kbC++202.5kb2024-11-18 17:33:542024-11-18 17:33:56

Judging History

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

  • [2024-11-18 17:33:56]
  • 评测
  • 测评结果:TL
  • 用时:503ms
  • 内存:1643924kb
  • [2024-11-18 17:33:54]
  • 提交

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 = 1e6 + 3;
const long long MOD = 1e7 + 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: 108ms
memory: 393952kb

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 152ms
memory: 549960kb

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: 176ms
memory: 549984kb

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: 95ms
memory: 393868kb

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 151ms
memory: 550124kb

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: 190ms
memory: 550100kb

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: 102ms
memory: 393804kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 120ms
memory: 471988kb

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: 139ms
memory: 471908kb

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: 124ms
memory: 472020kb

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: 79ms
memory: 393852kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 103ms
memory: 393948kb

input:

4
4 3 2 1
1 3 4 2

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 251ms
memory: 862592kb

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: 128ms
memory: 471956kb

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: 124ms
memory: 471964kb

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: 215ms
memory: 862628kb

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

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: 280ms
memory: 862712kb

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: 323ms
memory: 1018792kb

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: 315ms
memory: 1018948kb

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: 256ms
memory: 1018876kb

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: 448ms
memory: 1643816kb

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: 503ms
memory: 1643924kb

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: