#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<int>, 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 <typename T>↵
void printVec(vector<T> 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;↵
vector<int>arr(n);↵
for(int i=0;i<n;i++){↵
cin>>arr[i];↵
}↵
int op=0; vector<pair<int,int>>ans;↵
while(op<=50){↵
vector<int>v1(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;↵
}↵
}↵
↵
{↵
#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.net/problemset/problem/1854/A1↵
↵
↵
↵
↵
↵
↵
