Advertisement
999ms

Untitled

Oct 27th, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. ll Get(vector<ll>& a, int l, int r) {
  8.     if (r < 0) return 0;
  9.     if (l > r) return 0;
  10.     return a[r] - (l ? a[l - 1] : 0);
  11. }
  12.  
  13. int WhoWin(ll first, ll second, vector<ll>& sa, vector<ll>& sb, int i, int n, ll k) {
  14.     if (first < k && second >= k) return 1;
  15.     if (first >= k) return 2;
  16.     int left = i;
  17.     int right = n - 1;
  18.     int mid;
  19.     int res = n;
  20.     while (left <= right) {
  21.         mid = (left + right) / 2;
  22.         if (first + Get(sa, i, mid) >= k || second + Get(sb, i, mid) >= k) {
  23.             right = mid - 1;
  24.             res = mid;
  25.         } else {
  26.             left = mid + 1;
  27.         }
  28.     }
  29.     if (res == n) {
  30.         return 3;
  31.     }
  32.     if (first + Get(sa, i, res) >= k && second + Get(sb, i, res) >= k) {
  33.         return 3;
  34.     }
  35.     if (first + Get(sa, i, res) >= k) return 2;
  36.     return 1;
  37. }
  38.  
  39. void Solve() {
  40.     int n, k;
  41.     cin >> n >> k;
  42.     vector<ll> a(n), b(n);
  43.     for (int i = 0; i < n; i++) cin >> a[i];
  44.     for (int i = 0; i < n; i++) cin >> b[i];
  45.     vector<ll> sa, sb;
  46.     sa = a;
  47.     sb = b;
  48.     for (int i = 1; i < n; i++) {
  49.         sa[i] += sa[i - 1];
  50.         sb[i] += sb[i - 1];
  51.     }
  52.     if (WhoWin(0, 0, sa, sb, 0, n, k) == 1) {
  53.         cout << 0 << "\n";
  54.         cout << "\n";
  55.         return;
  56.     }
  57.     vector<int> ans;
  58.     ll first = 0;
  59.     ll second = 0;
  60.     for (int i = 0; i + 1 < n; i++) {
  61.         first += a[i];
  62.         second += b[i];
  63.         if (first >= k) {
  64.             cout << "-1\n";
  65.             return;
  66.         }
  67.         if (second >= k) {
  68.             cout << ans.size() << "\n";
  69.             for (int i : ans) {
  70.                 cout << i + 1 << " ";
  71.             }
  72.             cout << "\n";
  73.             return;
  74.         }
  75.         if (first + a[i + 1] >= k) {
  76.             ans.push_back(i);
  77.             ll dlt = min(first, second);
  78.             first -= dlt;
  79.             second -= dlt;
  80.         }
  81.         ll prefirst = first;
  82.         ll presecond = second;
  83.         ll dlt = min(first, second);
  84.         if (dlt > 0) {
  85.             prefirst = first - dlt;
  86.             presecond = second - dlt;
  87.             if (WhoWin(prefirst, presecond, sa, sb, i + 1, n, k) == 1) {
  88.                 ans.push_back(i);
  89.                 cout << ans.size() << "\n";
  90.                 for (int i : ans) cout << i + 1 << " ";
  91.                 cout << "\n";
  92.                 return;
  93.             }
  94.         }
  95.         if (WhoWin(first, second, sa, sb, i + 1, n, k) == 1) {
  96.             cout << ans.size() << "\n";
  97.             for (int i : ans) {
  98.                 cout << i + 1 << " ";
  99.             }
  100.             cout << "\n";
  101.             return;
  102.         }
  103.     }
  104.     cout << "-1\n";
  105. }
  106.  
  107. int main() {
  108.     ios_base::sync_with_stdio(false);
  109.     cin.tie(nullptr);
  110.     int t;
  111.     cin >> t;
  112.     while (t--) {
  113.         Solve();
  114.     }
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement