fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Speed
  5. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6. // Typedefs
  7. #define int long long
  8. #define pb push_back
  9. #define ff first
  10. #define ss second
  11. #define all(x) (x).begin(), (x).end()
  12. #define sz(x) ((int)(x).size())
  13. #define endl '\n'
  14.  
  15. void solve() {
  16.     int n, m;
  17.     cin >> n >> m;
  18.     vector<pair<int, int>> a(n);
  19.     for(int i = 0; i < n; i++) {
  20.         cin >> a[i].ff;
  21.         a[i].ss = i + 1; // Store 1-based index
  22.     }
  23.     // Sort by attack value (small to large)
  24.     sort(all(a));
  25.  
  26.     // Case 1: We want 0 survivors
  27.     if (m == 0) {
  28.         int sum_others = 0;
  29.         for(int i = 0; i < n - 1; i++) sum_others += a[i].ff;
  30.  
  31.         // If the sum of all smaller elves is enough to kill the king
  32.         if (sum_others >= a[n-1].ff) {
  33.             cout << n - 1 << endl;
  34.             // Everyone attacks the king
  35.             for(int i = 0; i < n - 1; i++) {
  36.                 cout << a[i].ss << " " << a[n-1].ss << endl;
  37.             }
  38.         } else {
  39.             cout << -1 << endl;
  40.         }
  41.         return;
  42.     }
  43.  
  44.     // Case 2: We want m survivors
  45.     // We try to save the 'm' largest elves and sacrifice the 'n-m' smallest.
  46.  
  47.     vector<pair<int, int>> moves;
  48.  
  49.     // We use the largest available survivor as the current "tank"
  50.     int target_idx = n - 1; 
  51.     int current_dmg = 0;
  52.  
  53.     // Iterate through attackers from Largest to Smallest (Greedy)
  54.     // Attackers are indices 0 to n-m-1
  55.     for(int i = n - m - 1; i >= 0; i--) {
  56.  
  57.         // Check if current tank is full
  58.         // We need: current_dmg + attacker_val < target_val 
  59.         // (Must be STRICTLY less so the target survives with at least 1 HP)
  60.         while (target_idx >= n - m && current_dmg + a[i].ff >= a[target_idx].ff) {
  61.             target_idx--;   // Move to the next strongest survivor
  62.             current_dmg = 0; // Reset damage for new tank
  63.         }
  64.  
  65.         // If we ran out of survivors to take the hits
  66.         if (target_idx < n - m) {
  67.             cout << -1 << endl;
  68.             return;
  69.         }
  70.  
  71.         // Assign attacker to current target
  72.         moves.pb({a[i].ss, a[target_idx].ss});
  73.         current_dmg += a[i].ff;
  74.     }
  75.  
  76.     // Output valid sequence
  77.     cout << sz(moves) << endl;
  78.     for(auto p : moves) {
  79.         cout << p.ff << " " << p.ss << endl;
  80.     }
  81. }
  82.  
  83. int32_t main() {
  84.     fast_io;
  85.     int t;
  86.     cin >> t;
  87.     while(t--) {
  88.         solve();
  89.     }
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
7
4 2
1 4 2 3
2 2
6 7
3 0
1 2 3
3 1
1 2 3
3 2
1 2 3
4 1
2 3 4 5
6 0
998244353 1000000000 314159265 676767677 999999999 987654321
stdout
copy 
2
3 2
1 2
0
2
1 3
2 3
-1
1
1 3
-1
5
3 2
4 2
6 2
1 2
5 2
https://ideone.com/ZUKNJL
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!