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_all = 0;
  20.     for(int i = 0; i < n; i++) {
  21.         cin >> a[i].ff;
  22.         a[i].ss = i + 1; // Store 1-based index
  23.         sum_all += a[i].ff;
  24.     }
  25.  
  26.     // Sort by value. 
  27.     // a[0] is smallest, a[n-1] is largest.
  28.     sort(all(a));
  29.  
  30.     // CASE 1: m = 0 (Kill everyone)
  31.     if (m == 0) {
  32.         // We need the sum of all n-1 elves to be enough to kill the nth elf.
  33.         int king_health = a[n-1].ff;
  34.         int damage_pool = sum_all - king_health;
  35.  
  36.         if (damage_pool < king_health) {
  37.             cout << -1 << endl;
  38.             return;
  39.         }
  40.  
  41.         cout << n - 1 << endl;
  42.         // Everyone attacks the King
  43.         // Smallest to largest attack the King
  44.         for(int i = 0; i < n - 1; i++) {
  45.             cout << a[i].ss << " " << a[n-1].ss << endl;
  46.         }
  47.         return;
  48.     }
  49.  
  50.     // CASE 2: m > 0 (Keep m survivors)
  51.     // We need m survivors to have "already attacked".
  52.     // This requires m victims.
  53.     // Total needed: m (survivors) + m (victims) = 2m.
  54.     if (n < 2 * m) {
  55.         cout << -1 << endl;
  56.         return;
  57.     }
  58.  
  59.     // Groups indices (in sorted array):
  60.     // Trash:    0  ... n - 2m - 1
  61.     // Targets:  n - 2m ... n - m - 1   (Count: m)
  62.     // Survivors: n - m ... n - 1       (Count: m)
  63.  
  64.     vector<pair<int, int>> moves;
  65.  
  66.     // 1. Process Trash
  67.     // Chain them: 0->1, 1->2 ... LastTrash -> FirstTarget
  68.     int first_target_idx = n - 2 * m;
  69.     for (int i = 0; i < first_target_idx; i++) {
  70.         // If it's the very last trash item, it attacks the first target
  71.         if (i == first_target_idx - 1) {
  72.              moves.pb({a[i].ss, a[first_target_idx].ss});
  73.         } else {
  74.              // Otherwise trash attacks next trash
  75.              moves.pb({a[i].ss, a[i+1].ss});
  76.         }
  77.     }
  78.  
  79.     // 2. Survivors attack Targets
  80.     // We pair S_i with T_i. 
  81.     // Survivor index: n - m + i
  82.     // Target index: n - 2m + i
  83.     for (int i = 0; i < m; i++) {
  84.         int surv_idx = n - m + i;
  85.         int targ_idx = n - 2 * m + i;
  86.         moves.pb({a[surv_idx].ss, a[targ_idx].ss});
  87.     }
  88.  
  89.     cout << sz(moves) << endl;
  90.     for(auto p : moves) {
  91.         cout << p.ff << " " << p.ss << endl;
  92.     }
  93. }
  94.  
  95. int32_t main() {
  96.     fast_io;
  97.     int t;
  98.     cin >> t;
  99.     while(t--) {
  100.         solve();
  101.     }
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 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 2
1 2
5 2
https://ideone.com/WhMjtj
language:
C++ (gcc 8.3)
created:
14 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!