Advertisement
Kevin_Zhang

Untitled

Jan 30th, 2022
1,052
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define pb emplace_back
  5. #define AI(i) begin(i), end(i)
  6. template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
  7. template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
  8. #ifdef KEV
  9. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  10. void kout() { cerr << endl; }
  11. template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
  12. template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
  13. #else
  14. #define DE(...) 0
  15. #define debug(...) 0
  16. #endif
  17. // My bug list :
  18. // integer overflow
  19. // 0based, 1based forgotten
  20. // index out of bound
  21. // n, m, i, j typo
  22. // some cases are missing
  23.  
  24. const int MAX_N = 300010, LG = 31, inf = 1e9;
  25.  
  26. int dp[MAX_N][2][2];
  27.  
  28. void solve() {
  29.     int n;
  30.     cin >> n;
  31.     vector<int> a(n), b(n);
  32.     for (int &i : a) cin >> i;
  33.     for (int &i : b) cin >> i;
  34.  
  35.     a.pb(0);
  36.     // I want to know if team B can win
  37.     // if values are the same, team A always win
  38.  
  39.     // j means number of team A removed
  40.     // k means number of team B removed
  41.  
  42.     for (int j : {0, 1}) for (int k : {0, 1})
  43.         dp[n][j][k] = (k == 1 ? inf : n * LG);
  44.     // yes, it's n * LG
  45.  
  46.     for (int i = n-1;i >= 0;--i) {
  47.         for (int j : {0, 1}) for (int k : {0, 1}) {
  48.             dp[i][j][k] = inf;
  49.             int l = 0, r = n * LG, m;
  50.  
  51.             auto valid = [&](int index) {
  52.                 // First we consider when k = 1 and we remove this one.
  53.                 if (k == 1 && dp[i+1][j][k-1] <= index)
  54.                     return true;
  55.                 // Then we are now sure that we keep b[i]
  56.                 int id = index / LG, t = index % LG, cv = b[i];
  57.                 while (id < n && cv > (a[id] >> t)) {
  58.                     ++id, t = 0, cv >>= 1;
  59.                 }
  60.                 int nxt = id * LG + t + 1;
  61.                 // case 1 : keep the id-th item
  62.                 if (dp[i+1][j][k] <= nxt)
  63.                     return true;
  64.                 // case 2 : remove id from team A
  65.                 if (j == 0) return false;
  66.                 id = min(n, id + 1), t = 0;
  67.                 while (id < n && cv > a[id]) {
  68.                     ++id, cv >>= 1;
  69.                 }
  70.                 return dp[i+1][0][k] <= id * LG + 1;
  71.             };
  72.  
  73.             while (l < r) {
  74.                 m = l + r >> 1;
  75.                 if (valid(m))
  76.                     r = m;
  77.                 else
  78.                     l = m+1;
  79.             }
  80.             dp[i][j][k] = l;
  81.         }
  82.     }
  83.     cout << (dp[0][1][1] == 0 ? "Yes" : "No") << '\n';
  84. }
  85. int32_t main() {
  86.     ios_base::sync_with_stdio(0), cin.tie(0);
  87.  
  88.     int T;
  89.     cin >> T;
  90.     while (T--)
  91.         solve();
  92. }
  93.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement