QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742023#7956. Walk Swappingyuto1115#WA 0ms3824kbC++201.3kb2024-11-13 15:39:252024-11-13 15:39:26

Judging History

This is the latest submission verdict.

  • [2024-11-13 15:39:26]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3824kb
  • [2024-11-13 15:39:25]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define eb emplace_back
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto b) {return a>b ? a=b, 1 : 0;}
bool chmax(auto& a, auto b) {return a<b ? a=b, 1 : 0;}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int n;
	cin >> n;
	vl A(n), b(n);
	rep(i, n) cin >> A[i];
	rep(i, n) cin >> b[i];
	rep(i, n) b.eb(b[i]);
	ll ans = inf;
	rep(_, 2) {
		rep(m, n) {
			vl a;
			rep(i, 2) {
				a.insert(a.end(), A.begin()+m, A.end());
				a.insert(a.end(), A.begin(), A.begin()+m);
			}
			vvl lb(2, vl(2*n+1));
			rep(k, 2) {
				lb[k][k] = k;
				rep2(i, k, 2*n) {
					if(a[i] == b[i-k]) lb[k][i+1] = lb[k][i];
					else lb[k][i+1] = i+1;
				}
			}
			if(lb[0].back() == 0) {
				chmin(ans, m*(n-1));
				continue;
			}
			rep(i, n) {
				ll r = lb[0][i+n];
				assert(r > i);
				if(lb[1][r] > i+1) continue;
				if(a[i] != b[r-1]) continue;
				chmin(ans, m*(n-1) + (r-i-1));
			}
		}
		reverse(all(A));
	}
	cout << (ans == inf ? -1 : ans) << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #8:

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

input:

5
4 3 5 2 1
1 3 5 4 2

output:

18

result:

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