fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define  ll long long
  4. #define  nl '\n'
  5. //#define  int long long
  6.  
  7. void file()
  8. {
  9. #ifndef ONLINE_JUDGE
  10.     freopen("in.txt", "r", stdin);
  11.     freopen("out.txt", "w", stdout);
  12. #else
  13.     // freopen("help.in", "r", stdin);
  14. #endif
  15. }
  16.  
  17. void solve()
  18. {
  19.     int n;
  20.     cin >> n;
  21.     vector<ll> a(n), b(n);
  22.     vector<int> bit(60);
  23.     for (int i = 0; i < n; i++)
  24.         cin >> a[i];
  25.  
  26.     for (int i = 0; i < n; i++)
  27.         cin >> b[i];
  28.  
  29.     ll need = 0;
  30.     vector<pair<int,ll>>v(n+9,{-1,-1});
  31.     vector<bool>vv(n+1);
  32.     vector<int>res(n+9);
  33.  
  34.     for (int i = 0;i<n;i++)
  35.     {
  36.         need = 0;
  37.         if ((a[i]&b[i]) != b[i])
  38.         {
  39.             need = (b[i] & ~a[i]);
  40.         }
  41.         if (need)
  42.         {
  43.             v[i] = {i,need};
  44.         }
  45.     }
  46.     ll prev = 0,idx = n;
  47.     for (int i = n-1;i>=0;i--)
  48.     {
  49.         if (a[i] & prev)
  50.         {
  51.             res[i+1]++;
  52.             res[idx+1]--;
  53.             ll tmp= (prev&a[i]);
  54.             prev&=(~tmp);
  55.             if (prev == 0)
  56.                 idx = n;
  57.         }
  58.         if (v[i].second !=-1)
  59.         {
  60.             prev |= v[i].second;
  61.             if (idx==n)
  62.                 idx = i;
  63.         }
  64.     }
  65.  
  66.     int ans = 0,cnt = 0;
  67.     for (int i = 1;i<=n;i++)
  68.         res[i]+=res[i-1];
  69.     for (int i = 1;i<n;i++)
  70.     {
  71.         if (res[i])
  72.             a[i]|=a[i-1],ans++;
  73.     }
  74.     for (int i = 0;i<n;i++)
  75.     {
  76.         if ((a[i]&b[i])!=b[i])
  77.         {
  78.             cout << -1<<nl;
  79.             return;
  80.         }
  81.     }
  82.  
  83.     cout << ans<<nl;
  84.  
  85.  
  86. }
  87.  
  88. signed main()
  89. {
  90.     ios::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     cout.tie(0);
  93.     file();
  94.  
  95.     int t = 1;
  96.     cin >> t;
  97.  
  98.     while (t--)
  99.     {
  100.         solve();
  101.     }
  102.  
  103.  
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7zjSKa
language:
C++14 (gcc 8.3)
created:
11 hours 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!