include <bits/stdc++.h>

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace __gnu_pbds;

define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>

typedef long long ll; typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

typedef long long ll; typedef long double ld;

define all(x) x.begin(), x.end()

define debug(x) cout << #x << '-' << x << endl;

define VecTop(v) v.size() — 1

define pb push_back

define pf push_front

const int MOD = 1e9 + 7;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

bool isPrime(ll n) { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; }

ll super_power(ll base, ll power) { ll res = 1; while (power > 0) { if (power & 1) res = (res * base); power >>= 1; base = (base * base); } return res; }

template void printVec(vector v) { for (auto val : v) { cout << val << ' '; } cout << endl; }

// HOPE YOU HAVE A CLEAR PICTURE OF THE ALGORITHM // Deep breaths, everything is cool

bool testcases = true;

void solve() { int n; cin>>n; vectorarr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } int op=0; vector<pair<int,int>>ans; while(op<=50){ vectorv1(arr.begin(),arr.end()); sort(v1.begin(),v1.end()); int mxele= v1[v1.size()-1]; int mxelei= max_element(arr.begin(),arr.end())-arr.begin(); int breakpnt=-1; for(int i=1;i<n;i++){ if(arr[i]<arr[i-1]){ breakpnt=i; break; } } if(breakpnt==-1) break; int req= (arr[breakpnt-1]-arr[breakpnt])/mxele ; arr[breakpnt]= arr[breakpnt]+ req*mxele; op= op+req; while(req--){ ans.push_back({breakpnt,mxelei}); } if(arr[breakpnt]<arr[breakpnt-1]){ int extra=arr[breakpnt-1]-arr[breakpnt]; //cout<<*lower_bound(v1.begin(),v1.end(),extra)<<endl; op++; int x=*lower_bound(v1.begin(),v1.end(),extra); for(int i=0;i<n;i++){ if(arr[i]==x){ ans.push_back({breakpnt,i}); break; } } arr[breakpnt]= arr[breakpnt]+ *lower_bound(v1.begin(),v1.end(),extra); //cout<<arr[breakpnt]<<endl; } if(is_sorted(arr.begin(),arr.end())) break; } // if(is_sorted(arr.begin(),arr.end())){cout<<"yes"<<endl;} // else cout<<"NO"<<endl; cout<<ans.size()<<endl; for(auto it:ans){ cout<<it.first+1<<" "<<it.second+1<<endl; } }

int main() { #ifndef ONLINE_JUDGE freopen("input1.txt", "r", stdin); freopen("output1.txt", "w", stdout); #endif cin.tie(0); cin.sync_with_stdio(0); cout.tie(0); cout.sync_with_stdio(0); int T = 1; if (testcases) cin >> T; while (T--) { solve(); } return 0; }

/* stuff you should look for * constraints * int overflow, array bounds * special cases, corner cases * dry run shit * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH * sort() — O(N*log(N)) — At 10^5 ~= 10^6 ; * Basically take MOD everywhere */

The above approach is giving MLE on test case 2 and i cant understand why. Please help Problem link: https://codeforces.me/problemset/problem/1854/A1