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.     int sum_others = 0;
  20.  
  21.     for(int i = 0; i < n; i++) {
  22.         cin >> a[i].ff;
  23.         a[i].ss = i + 1; // Store original 1-based index
  24.     }
  25.  
  26.     // Sort elves by value (smallest to largest)
  27.     sort(all(a));
  28.  
  29.     // --- CASE 1: m = 0 (Kill Everyone) ---
  30.     if (m == 0) {
  31.         // Calculate sum of all attackers (excluding the King at n-1)
  32.         int current_king_hp = a[n-1].ff;
  33.         for(int i = 0; i < n - 1; i++) sum_others += a[i].ff;
  34.  
  35.         // Impossible if we lack the damage to kill the King
  36.         if (sum_others < current_king_hp) {
  37.             cout << -1 << endl;
  38.             return;
  39.         }
  40.  
  41.         vector<pair<int, int>> moves;
  42.         // Logic: Attack King if he can survive it. If not, waste the attacker on the next elf.
  43.         // We MUST ensure the King only dies on the very last attack.
  44.         for(int i = 0; i < n - 1; i++) {
  45.             // If this is the LAST attacker, we must attack the King to finish the game.
  46.             if (i == n - 2) {
  47.                 moves.pb({a[i].ss, a[n-1].ss});
  48.             }
  49.             // If King can survive this attack, hit him.
  50.             else if (current_king_hp > a[i].ff) {
  51.                 moves.pb({a[i].ss, a[n-1].ss});
  52.                 current_king_hp -= a[i].ff;
  53.             }
  54.             // If King would die too early, waste this attacker on the next attacker.
  55.             else {
  56.                 moves.pb({a[i].ss, a[i+1].ss});
  57.                 // a[i] dies. a[i+1] takes damage but survives (since a[i+1] > a[i]).
  58.                 // We don't need to track a[i+1]'s health precisely, just know it lives.
  59.             }
  60.         }
  61.  
  62.         cout << sz(moves) << endl;
  63.         for(auto p : moves) cout << p.ff << " " << p.ss << endl;
  64.         return;
  65.     }
  66.  
  67.     // --- CASE 2: m > 0 (Keep m Survivors) ---
  68.  
  69.     // We need m victims for m survivors to safely "attack" and lock themselves.
  70.     // Constraint: n must be at least 2*m
  71.     if (n < 2 * m) {
  72.         cout << -1 << endl;
  73.         return;
  74.     }
  75.  
  76.     // Groups logic (based on sorted array):
  77.     // Trash:     Indices 0 to (n - 2m - 1)
  78.     // Targets:   Indices (n - 2m) to (n - m - 1)
  79.     // Survivors: Indices (n - m) to (n - 1)
  80.  
  81.     vector<pair<int, int>> moves;
  82.  
  83.     // 1. Process Trash (Chain them to get rid of them)
  84.     int trash_count = n - 2 * m;
  85.     int first_target_idx = n - 2 * m;
  86.  
  87.     if (trash_count > 0) {
  88.         for (int i = 0; i < trash_count; i++) {
  89.             if (i == trash_count - 1) {
  90.                 // Last trash attacks the first target
  91.                 moves.pb({a[i].ss, a[first_target_idx].ss});
  92.             } else {
  93.                 // Trash attacks next trash
  94.                 moves.pb({a[i].ss, a[i+1].ss});
  95.             }
  96.         }
  97.     }
  98.  
  99.     // 2. Survivors attack Targets
  100.     // We pair Survivor[k] with Target[k]
  101.     for (int i = 0; i < m; i++) {
  102.         int target_idx = n - 2 * m + i;
  103.         int survivor_idx = n - m + i;
  104.  
  105.         // Survivor attacks Target
  106.         // Survivor is stronger, so Survivor lives. Target dies.
  107.         moves.pb({a[survivor_idx].ss, a[target_idx].ss});
  108.     }
  109.  
  110.     // Output
  111.     cout << sz(moves) << endl;
  112.     for(auto p : moves) {
  113.         cout << p.ff << " " << p.ss << endl;
  114.     }
  115. }
  116.  
  117. int32_t main() {
  118.     fast_io;
  119.     int t;
  120.     cin >> t;
  121.     while(t--) {
  122.         solve();
  123.     }
  124.     return 0;
  125. }
Success #stdin #stdout 0s 5320KB
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
4 1
2 3
-1
2
1 3
2 3
2
1 2
3 2
-1
3
1 2
2 3
4 3
5
3 2
4 2
6 1
1 5
5 2
https://ideone.com/Y3Y7cu
language:
C++ (gcc 8.3)
created:
13 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!