1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ALL(x) x.begin(),x.end()
  7. #define SORT(x) sort(ALL(x))
  8. #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
  9. #define REP(a,b) FOR(a,0,b)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define vl vector<ll>
  15. #define vi vector<int>
  16. #define f first
  17. #define s second
  18. #define yy cout<<"YES"<<endl;return
  19. #define nn cout<<"NO"<<endl;return
  20. #define minus1 cout<<-1<<endl;return
  21. #define rd(a,x) REP(i,x)cin >> a[i]
  22. int ttt = 1, case_ = 0;
  23. ll n, m, k;
  24. string S;
  25. template <class myType>
  26. void print_arr(myType &arr, ll L, string sep){
  27. REP(i,L){ cout << arr[i] << (i < L-1 ? sep : "\n"); }
  28. return; }
  29. /*
  30. Solve the smallest problem I can at any time
  31. I can add index k to my pile when at least (k - 1)/2 problems have been solved
  32. When 0 problems solved, indices 0 and 1
  33. When 1 problem solved, indices 2 and 3
  34. When 2 problems solved, indices 4 and 5
  35. Etc
  36. */
  37. void solve() {
  38. cin >> n >> k;
  39. vl a(n);
  40. rd(a, n);
  41. priority_queue<pll, vector<pll>, greater<pll>> q;
  42. ll solved = 0, t = 0;
  43. vl ans;
  44. vector<bool> used(n, 0);
  45. while (1) {
  46. // add all problems I am now allowed to solve to the priority queue
  47. vl targ = {2*solved, 2*solved + 1};
  48. for(ll j: targ) {
  49. if (j >= n) continue;
  50. if (used[j]) continue;
  51. used[j] = 1;
  52. q.push(mp(a[j], j+1));
  53. }
  54. // if there are no problems in the PQ, I can't do anything, so break
  55. if (q.empty()) {
  56. break;
  57. }
  58. // take the shortest problem from the PQ. If it's too long to solve, break
  59. if (q.top().f + t <= k) {
  60. t += q.top().f;
  61. solved++;
  62. ans.pb(q.top().s);
  63. q.pop();
  64. }
  65. else {
  66. break;
  67. }
  68. }
  69. cout << solved << endl;
  70. if (solved) print_arr(ans, solved, " ");
  71. else cout << endl;
  72. return;
  73. }
  74. int main() {
  75. quick;
  76. cin >> ttt;
  77. while (ttt--) solve();
  78. return 0;
  79. }
Comments powered by Disqus