fork download
copy 
  1. /// Remainder Game Atcoder
  2. /// Author: PmQwerty
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. const int MAXN = 51;
  6. const long long INF = 1e18;
  7. int a[MAXN];
  8. int b[MAXN];
  9. int n;
  10. vector<int> s;
  11. long long d[MAXN][MAXN];
  12. void floyd(int l){
  13.     for (int i = 0; i <= 50; i++){
  14.          for (int j = 0; j <= 50; j++) d[i][j] = INF;
  15.     }
  16.     for (int i = 0; i <= 50; i++) d[i][i] = 0;
  17.     for (int i = 0; i <= 50; i++){
  18.          for (int j = 1; j < l; j++){
  19.               d[i][i % j] = min(d[i][i % j], (1LL << j));
  20.          }
  21.     }
  22.     for (int i = 0; i <= 50; i++){
  23.          for (int j: s){
  24.               d[i][i % j] = min(d[i][i % j], (1LL << j));
  25.          }
  26.     }
  27.     for (int k = 0; k <= 50; k++){
  28.          for (int i = 0; i <= 50; i++){
  29.               for (int j = 0; j <= 50; j++){
  30.                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  31.               }
  32.          }
  33.     }
  34. }
  35. int main(){
  36.     ios_base::sync_with_stdio(0);
  37.     cin.tie(0);
  38.     cin >> n;
  39.     for (int i = 1; i <= n; i++) cin >> a[i];
  40.     for (int i = 1; i <= n; i++) cin >> b[i];
  41.     floyd(51);
  42.     for (int i = 1; i <= n; i++){
  43.          if (d[a[i]][b[i]] == INF){
  44.              cout << -1 << '\n';
  45.              return 0;
  46.          }
  47.     }
  48.     for (int i = 50; i >= 1; i--){
  49.          floyd(i);
  50.          for (int j = 1; j <= n; j++){
  51.               if (d[a[j]][b[j]] == INF){
  52.                   s.push_back(i);
  53.                   break;
  54.               }
  55.          }
  56.     }
  57.     long long ans = 0;
  58.     for (int x: s) ans += (1LL << x);
  59.     cout << ans << '\n';
  60. }
  61.  
Success #stdin #stdout 0.02s 5288KB
comments (?)
stdin
copy 
3
19 10 14
0 3 4
stdout
copy 
160
https://ideone.com/7ES99T
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!