Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- using ll = long long;
- ll Get(vector<ll>& a, int l, int r) {
- if (r < 0) return 0;
- if (l > r) return 0;
- return a[r] - (l ? a[l - 1] : 0);
- }
- int WhoWin(ll first, ll second, vector<ll>& sa, vector<ll>& sb, int i, int n, ll k) {
- if (first < k && second >= k) return 1;
- if (first >= k) return 2;
- int left = i;
- int right = n - 1;
- int mid;
- int res = n;
- while (left <= right) {
- mid = (left + right) / 2;
- if (first + Get(sa, i, mid) >= k || second + Get(sb, i, mid) >= k) {
- right = mid - 1;
- res = mid;
- } else {
- left = mid + 1;
- }
- }
- if (res == n) {
- return 3;
- }
- if (first + Get(sa, i, res) >= k && second + Get(sb, i, res) >= k) {
- return 3;
- }
- if (first + Get(sa, i, res) >= k) return 2;
- return 1;
- }
- void Solve() {
- int n, k;
- cin >> n >> k;
- vector<ll> a(n), b(n);
- for (int i = 0; i < n; i++) cin >> a[i];
- for (int i = 0; i < n; i++) cin >> b[i];
- vector<ll> sa, sb;
- sa = a;
- sb = b;
- for (int i = 1; i < n; i++) {
- sa[i] += sa[i - 1];
- sb[i] += sb[i - 1];
- }
- if (WhoWin(0, 0, sa, sb, 0, n, k) == 1) {
- cout << 0 << "\n";
- cout << "\n";
- return;
- }
- vector<int> ans;
- ll first = 0;
- ll second = 0;
- for (int i = 0; i + 1 < n; i++) {
- first += a[i];
- second += b[i];
- if (first >= k) {
- cout << "-1\n";
- return;
- }
- if (second >= k) {
- cout << ans.size() << "\n";
- for (int i : ans) {
- cout << i + 1 << " ";
- }
- cout << "\n";
- return;
- }
- if (first + a[i + 1] >= k) {
- ans.push_back(i);
- ll dlt = min(first, second);
- first -= dlt;
- second -= dlt;
- }
- ll prefirst = first;
- ll presecond = second;
- ll dlt = min(first, second);
- if (dlt > 0) {
- prefirst = first - dlt;
- presecond = second - dlt;
- if (WhoWin(prefirst, presecond, sa, sb, i + 1, n, k) == 1) {
- ans.push_back(i);
- cout << ans.size() << "\n";
- for (int i : ans) cout << i + 1 << " ";
- cout << "\n";
- return;
- }
- }
- if (WhoWin(first, second, sa, sb, i + 1, n, k) == 1) {
- cout << ans.size() << "\n";
- for (int i : ans) {
- cout << i + 1 << " ";
- }
- cout << "\n";
- return;
- }
- }
- cout << "-1\n";
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int t;
- cin >> t;
- while (t--) {
- Solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement