fork download
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. #define int long long
  6. #define oset tree < pair<int, int> , null_type , less<pair<int, int>> , rb_tree_tag , tree_order_statistics_node_update >
  7. using namespace std;
  8. signed main(){
  9. //Pain has a strength of Z
  10. //There are N soldiers
  11. //The power of the ith solider is A(i)
  12. //So when the ith soldier attacks pain
  13. //Z = Z - A(i);
  14. //A(i) = A(i)/2;
  15. //Pain is defeated when his strength becomes <= 0
  16.  
  17. //Dp, greedy
  18. //DP[Z] -> won't pass
  19. //Greedy?
  20. //Find an optimal approach to defeat pain
  21. //The optimal approach would be that the soldier with max power attacks pain
  22. //His power becomes halved
  23. //The solider with the new maximum power attacks Pain
  24. //This process is repeated until all soldiers have strength 0 (soliders have lost) or Pain has strength 0 (soldiers have won)
  25.  
  26. //How would we implement this?
  27.  
  28. //We need a data structures where we can:
  29. //Find the maximum element in O(1) or O(LogN) -> Priority queue can do
  30. //Remove the maximum element in O(1) or O(LogN) -> Priority queue can do
  31. //Insert a new element in O(1) or O(LogN) -> Priority queue can do this
  32. //Can store duplicate elements -> Priority queue can do this
  33.  
  34. //Priority queue?
  35.  
  36. int t;
  37. cin>>t;
  38. while(t--){
  39. //N -> number of soldiers
  40. //Z -> the strength of Pain
  41. int n, z;
  42. cin>>n>>z;
  43. int a[n]; //A -> the power of soldiers
  44. for(int i = 0;i<n;i++) cin>>a[i];
  45. int ans = 0; //The answer
  46. priority_queue<int> pq;
  47. for(int i = 0;i<n;i++) pq.push(a[i]); //inserting powers into the priority queue
  48. //Max strength of any soldier is 0
  49. while(z>0 && pq.top()>0){
  50. int attack = pq.top(); //This is the strength of the attack
  51. z = z - attack;
  52. pq.pop(); //We have used this attack power, we can't use it again
  53. pq.push((attack/2));
  54. ans++;
  55. }
  56. if(z>0) cout<<"Evacuate"<<endl; //pain was not defeated
  57. else cout<<ans<<endl;
  58. }
  59. }
  60. //acdabcd
  61.  
Success #stdin #stdout 0s 4488KB
stdin
Standard input is empty
stdout
2