QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710225 | #7956. Walk Swapping | ucup-team3646 | WA | 100ms | 3964kb | C++20 | 2.8kb | 2024-11-04 19:07:11 | 2024-11-04 19:07:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define rep2(i,l,r) for(ll i=ll(l); i<ll(r); i++)
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
#define all(A) A.begin,A.end()
#define elif else if
using pii = pair<ll, ll>;
template<class T>
bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}
template<class T>
bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>
void print(vector<T> a) {
for (auto x : a) cerr << x << ' ';
cout << endl;
}
template<class T>
void print(T x) {
cerr << x << '\n';
}
template<class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
cerr << head << ' ';
print(forward<Tail>(tail)...);
}
constexpr ll mod = 1e9 + 7;
int B = 1234567;
int invB = 989145189;
int B2 = 123456;
int invB2 = 78351802;
int inf=1<<30;
vll powB(3010,1),powinvB(3010,1);
vll powB2(3010,1),powinvB2(3010,1);
int calc(int n,vi a,vi b){
unordered_map<ll,vi>S;
rep(off,n){
ll h=0;
ll h2=0;
rep(i,n){
h+=powB[i]*b[(i-off+n)%n];
h%=mod;
h2+=powB2[i]*b[(i-off+n)%n];
h2%=mod;
}
S[(h<<30)|h2].push_back(off);
// print(off,h);
}
int ans=inf;
auto upd_ans=[&](ll h1,ll h2,int tmp)->void{
ll h=(h1<<30)|h2;
if(S.find(h)!=S.end()){
auto it=lower_bound(S[h].begin(),S[h].end(),0);
int res=(n-1)*(*it)+tmp;
ans=min(ans,res);
// print("!!!!",tmp,res);
}
};
rep(i,n){
vll res(n,0);
vll res2(n,0);
rep(j,n)res[j]=powB[j]*a[j]%mod;
rep(j,n)res2[j]=powB2[j]*a[j]%mod;
ll h=0;
ll h2=0;
rep(j,n){
h+=res[j];
h%=mod;
h2+=res2[j];
h2%=mod;
}
upd_ans(h,h2,0);
int l=i;
rep2(t,1,n){
int r=(l+1)%n;
h+=mod-res[l];
h+=mod-res[r];
h2+=mod-res2[l];
h2+=mod-res2[r];
res[l]=a[r]*powB[l]%mod;
res[r]=a[i]*powB[r]%mod;
res2[l]=a[r]*powB2[l]%mod;
res2[r]=a[i]*powB2[r]%mod;
h+=res[l];
h+=res[r];
h2+=res2[l];
h2+=res2[r];
h%=mod;
h2%=mod;
upd_ans(h,h2,t);
// print(res);
l+=1;
l%=n;
}
}
return ans;
}
void solve() {
int n;
cin>>n;
vi a(n),b(n);
rep(i,n)cin>>a[i];
rep(i,n)cin>>b[i];
int ans1=calc(n,a,b);
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int ans2=calc(n,a,b);
int ans=min(ans1,ans2);
if(ans1==inf)ans=-1;
cout<<ans<<endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
rep2(i,1,3010){
powB[i]=powB[i-1]*B%mod;
powinvB[i]=powinvB[i-1]*invB%mod;
powB2[i]=powB2[i-1]*B%mod;
powinvB2[i]=powinvB2[i-1]*invB2%mod;
}
solve();
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: 1ms
memory: 3708kb
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: 1ms
memory: 3640kb
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: 1ms
memory: 3708kb
input:
4 1 2 3 4 4 2 1 3
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3648kb
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: 1ms
memory: 3636kb
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: 3620kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3688kb
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: 1ms
memory: 3692kb
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: 3712kb
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: 1ms
memory: 3716kb
input:
4 4 3 2 1 1 3 2 4
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
4 4 3 2 1 1 3 4 2
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3684kb
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: 1ms
memory: 3636kb
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: 1ms
memory: 3636kb
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: 3620kb
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: 3720kb
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: 1ms
memory: 3652kb
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: 1ms
memory: 3628kb
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: 1ms
memory: 3684kb
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: 1ms
memory: 3708kb
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: 1ms
memory: 3628kb
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: 3648kb
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: 1ms
memory: 3720kb
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: 3856kb
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: 1ms
memory: 3648kb
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: 1ms
memory: 3716kb
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: 1ms
memory: 3632kb
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: 1ms
memory: 3684kb
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: 1ms
memory: 3636kb
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: 0ms
memory: 3632kb
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: 1ms
memory: 3712kb
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: 1ms
memory: 3636kb
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: 100ms
memory: 3964kb
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:
194244
result:
wrong answer 1st lines differ - expected: '243210', found: '194244'