QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303611#7956. Walk SwappingPPP#WA 1ms5636kbC++173.2kb2024-01-12 20:09:402024-01-12 20:09:41

Judging History

This is the latest submission verdict.

  • [2024-01-12 20:09:41]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5636kb
  • [2024-01-12 20:09:40]
  • Submitted

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

typedef long long ll;
typedef long double ld;
int n;
const int maxN = 6005;
int lcp[maxN][maxN];
int A[maxN], B[maxN];
vector<int> x, y;
int solve() {
    for (int i = 0; i < n; i++) {
        A[i] = A[i + n] = x[i];
        B[i] = B[i + n] = y[i];
    }
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) {
            if (A[i] != B[j]) lcp[i][j] = 0;
            else if (i > 0 && j > 0) lcp[i][j] = lcp[i - 1][j - 1] + 1;
            else lcp[i][j] = 1;
        }
    }
    int best = 1e9;
    for (int p = 0; p < n; p++) {
        //circles
        for (int c = 0; c < n - 1; c++) {
            int from_a = p + c;
            from_a %= n;
            from_a += n;
            int from_b = p + n - 1;
            from_b %= n;
            from_b += n;

            int X = min(lcp[from_a][from_b], c);

            int len_c = X;
            if (len_c == c) {
                //it + n - 1
                from_a = p + n - 1;
                from_a %= n;
                from_a += n;

                from_b = p + n - 1 - c;
                from_b %= n;
                from_b += n;
                int Y = min(lcp[from_a][from_b], n - 1 - c);
                len_c += Y;
                if (len_c == n - 1) {
                    if (A[p] == B[p]) {
                        len_c++;
                    }
                }
            }
            if (len_c == n) {
                best = min(best, c * n);
                break;
            }
            int lft = n - len_c;
            if (lft == 1) {
                continue;
            }
            if (lft <= n - 1 - c + 1) {
                if (B[p] != A[(p + c + 1) % n]) continue;
                int from_a = (p + c + lft - 1) % n;
                from_a += n;
                int from_b = (p + lft - 2) % n;
                from_b += n;
                if (lcp[from_a][from_b] >= lft - 2 && A[p] == B[(p + lft - 1) % n]) {
                    best = min(best, c * n + lft);
                    break;
                }
            }
            else {
                if (A[p] != B[p + lft - 1]) continue;
                if (B[p] != B[p + c + 1]) continue;
                int D = lft - (n - c);
                if (lcp[p + D][p + lft - 2] < D) continue;
                if (lcp[p + n - 1][p + n - 2 - c] < n - 2 - c) continue;
                best = min(best, c * n + lft);
                break;
            }
        }
    }
    return best;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin >> n;
    x.resize(n);
    y.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> y[i];
    }
    int best = 1e9;
    for (int it = 0; it < 2; it++) {
        best = min(best, solve());
        reverse(x.begin(), x.end());
        reverse(y.begin(), y.end());
    }
    if (best > 1e8) {
        best = 0;
    }
    cout << best - 1;
    return 0;
}  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

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

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

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

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

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

input:

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

output:

11

result:

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