QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488780 | #7956. Walk Swapping | arnold518 | WA | 212ms | 4148kb | C++17 | 2.4kb | 2024-07-24 15:17:29 | 2024-07-24 15:17:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3000;
const int INF = 1e9;
const int MOD = 998244353;
struct mint
{
int x;
mint() : x(0) {}
mint(int _x) : x(_x) {}
mint operator + (int ot) const { return x+ot>=MOD ? x+ot-MOD : x+ot; }
mint operator - (int ot) const { return x<ot ? x+MOD-ot : x-ot; }
mint operator - () const { return x ? MOD-x : 0; }
mint operator * (int ot) const { return 1ll*x*ot%MOD; }
mint operator += (int ot) { return *this = *this + ot; }
mint operator -= (int ot) { return *this = *this - ot; }
mint operator *= (int ot) { return *this = *this * ot; }
operator int() const { return x; }
};
mint mpow(mint a, ll b)
{
mint ret=1;
while(b)
{
if(b&1) ret*=a;
b>>=1; a=a*a;
}
return ret;
}
mint inv(mint a) { return mpow(a, MOD-2); }
int N, A[MAXN+10], B[MAXN+10];
mint PP[MAXN+10], IP[MAXN+10];
mint HA[MAXN+10], HB[MAXN+10];
int ans=INF;
void solve()
{
for(int cyc=0; cyc<N; cyc++)
{
vector<pii> V;
for(int i=1; i<=N; i++) HA[i]=HA[i-1]+PP[i]*mint(A[i]);
for(int i=1; i<=N; i++) HB[i]=HB[i-1]+PP[i]*mint(B[i]);
for(int i=1; i<=N; i++) V.push_back({HB[i-1]+(HB[N]-HB[i])*IP[1], i});
sort(V.begin(), V.end());
for(int i=2; i<=N; i++)
{
mint val = (HA[N]-HA[i-1])*IP[i-1] + (HA[i-1]-HA[1])*PP[N-i];
auto it=lower_bound(V.begin(), V.end(), pii(val.x, 0));
if(it!=V.end() && it->first==val.x)
{
ans=min(ans, (i-2)*N+it->second-1);
}
}
rotate(A+1, A+2, A+N+1);
rotate(B+1, B+2, B+N+1);
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
for(int i=1; i<=N; i++) scanf("%d", &B[i]);
if(N==1)
{
if(A[1]==B[1]) printf("0\n");
else printf("-1\n");
return 0;
}
PP[0]=1; IP[0]=1;
PP[1]=29; IP[1]=inv(PP[1]);
for(int i=2; i<=N; i++) PP[i]=PP[i-1]*PP[1];
for(int i=2; i<=N; i++) IP[i]=IP[i-1]*IP[1];
solve();
reverse(A+1, A+N+1);
reverse(B+1, B+N+1);
solve();
if(ans==INF) printf("-1\n");
else printf("%d\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4128kb
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: 3848kb
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: 3876kb
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: 3848kb
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: 3944kb
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: 4148kb
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: 3872kb
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: 0ms
memory: 3848kb
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: 0ms
memory: 3868kb
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: 0ms
memory: 3844kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
4 4 3 2 1 1 3 4 2
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3736kb
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: 0ms
memory: 4128kb
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: 0ms
memory: 3804kb
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: 0ms
memory: 3804kb
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: 0ms
memory: 3928kb
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: 0ms
memory: 3844kb
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: 0ms
memory: 3872kb
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: 0ms
memory: 4148kb
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: 0ms
memory: 4080kb
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: 0ms
memory: 4148kb
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: 0ms
memory: 3928kb
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: 0
Accepted
time: 2ms
memory: 3872kb
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:
109
result:
ok single line: '109'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3852kb
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 100 ...
output:
89
result:
ok single line: '89'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3944kb
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 51 5...
output:
4924
result:
ok single line: '4924'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3840kb
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 51 5...
output:
4905
result:
ok single line: '4905'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
100 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 1...
output:
3990
result:
ok single line: '3990'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
100 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...
output:
125
result:
ok single line: '125'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
100 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 9 9 9 9 9 10 10 10 10 10 11 11 11 15 11 1...
output:
-1
result:
ok single line: '-1'
Test #31:
score: 0
Accepted
time: 2ms
memory: 4132kb
input:
100 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...
output:
79
result:
ok single line: '79'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
100 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...
output:
-1
result:
ok single line: '-1'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
100 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
output:
0
result:
ok single line: '0'
Test #34:
score: -100
Wrong Answer
time: 212ms
memory: 3864kb
input:
1000 458 51 4 190 103 444 401 456 34 970 169 517 283 66 571 282 233 161 32 376 168 616 993 347 213 597 334 652 471 532 552 987 353 613 665 305 477 632 331 293 939 598 175 813 10 890 423 560 502 857 277 18 283 461 6 231 233 648 929 75 896 807 900 2 582 84 81 107 255 145 909 562 492 58 218 575 7 610 6...
output:
57662
result:
wrong answer 1st lines differ - expected: '243210', found: '57662'