QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711708#7956. Walk Swappingkizen#WA 0ms3856kbC++203.1kb2024-11-05 13:07:052024-11-05 13:07:06

Judging History

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

  • [2024-11-05 13:07:06]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-11-05 13:07:05]
  • 提交

answer

#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif

#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi array<int, 2>
#define comp(v) (sort(all(v)), v.erase(unique(all(v)), v.end()))
#define lb(v, x) (lower_bound(all(v), x) - v.begin())
#define MIN(x, y) (x = min(x, y))

using namespace std;

#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    // n = 3000;
    vector<int> a(n), inb(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        // a[i] = 1;
        --a[i];
    }
    for(int i = 0; i < n; ++i){
        cin >> inb[i];
        // inb[i] = 1;
        --inb[i];
    }

    if(n == 1){
        cout << (a[0] == inb[0] ? 0 : -1);
        return 0;
    }
    else if(n == 2){
        if(a == inb) cout << 0;
        else if(a[0] == inb[1] && a[1] == inb[0]) cout << 1;
        else cout << -1;
        return 0;
    }

    int ans = (int)1e18;
    for(int rr = 0; rr < 2; ++rr){
        auto b = inb;
        for(int i = 0; i < n; ++i){
            b.pb(b[i]);
        }

        vector<vector<int>> pos(n);
        for(int i = 0; i < n * 2; ++i){
            pos[b[i]].pb(i);
        }

        auto sol2 = [&](vector<int> x){
            for(int i = 0; i < n; ++i) x.pb(x[i]);
            int same = 0;
            for(int i = 0; i < n; ++i){
                if(x[i] == b[i]){
                    same = 1;
                    break;
                }
            }
            if(!same) return (int)1e18;

            int sp = 0, rp = 0;
            int rv = (int)1e18;
            for(int i = n - 1; i >= 0; --i){
                if(x[i] != b[i]){
                    sp = i;
                    break;
                }
            }
            for(int i = 0; i < n; ++i){
                if(x[i + n - 1] != b[i + n - 1]) sp = i + n - 1;
                rp = max(rp, i);
                while(rp + 1 < n * 2 && b[rp] == x[rp + 1]){
                    ++rp;
                }

                int l = max(i + 1, sp), r = min(rp, i + n - 2);
                if(l <= r){
                    int p = lb(pos[x[i]], l);
                    if(p < sz(pos[x[i]]) && pos[x[i]][p] <= r){
                        // cout << i << ' ' << pos[x[i]][p] << endl;
                        MIN(rv, pos[x[i]][p] - i);
                    }
                }
            }
            return rv;
        };
        auto sol1 = [&](vector<int> x){
            for(int rep = 1; rep < n; rep += n - 2){
                for(int i = 0, now = 0; i < n; ++i){
                    MIN(ans, now + sol2(x));

                    now += n - 1;
                    rotate(x.begin(), x.begin() + rep, x.end());
                }
                if(n <= 2) break;
            }
        };
        sol1(a);

        reverse(all(a));
        reverse(all(inb));
    }

    if(ans == (int)1e18) ans = -1;
    cout << ans << '\n';

    // cout << clock() / (double)CLOCKS_PER_SEC;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

input:

5
4 3 5 2 1
1 3 5 4 2

output:

2

result:

ok single line: '2'

Test #9:

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

input:

5
4 3 5 2 1
1 4 3 5 2

output:

-1

result:

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