QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710189#7956. Walk Swappingucup-team3646WA 80ms3916kbC++202.3kb2024-11-04 19:00:472024-11-04 19:00:49

Judging History

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

  • [2024-11-04 19:00:49]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:3916kb
  • [2024-11-04 19:00:47]
  • 提交

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 = 100;
// int invB = 570000004;


int B=10;
int invB=700000005;

int inf=1<<30;
vll powB(3010,1),powinvB(3010,1);

int calc(int n,vi a,vi b){
  unordered_map<ll,vi>S;
  rep(off,n){
    ll h=0;
    rep(i,n){
      h+=powB[i]*b[(i-off+n)%n];
      h%=mod;
    }
    S[h].push_back(off);
    // print(off,h);
  }

  int ans=inf;

  auto upd_ans=[&](ll h,int tmp)->void{
    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);
    rep(j,n)res[j]=powB[j]*a[j]%mod;
    ll h=0;
    rep(j,n)h+=res[j];
    h%=mod;
    upd_ans(h,0);
    int l=i;
    rep2(t,1,n){
      int r=(l+1)%n;
      h+=mod-res[l];
      h+=mod-res[r];
      res[l]=a[r]*powB[l]%mod;
      res[r]=a[i]*powB[r]%mod;
      h+=res[l];
      h+=res[r];
      h%=mod;
      upd_ans(h,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;
  }

  solve();

  return 0;
}

详细

Test #1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 0ms
memory: 3548kb

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

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

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: 0ms
memory: 3568kb

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

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

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: 1ms
memory: 3576kb

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

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

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: 80ms
memory: 3732kb

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:

97872

result:

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