C. Differential Sorting || Codeforces Round #772 (Div. 2)

 LINK: C. Differential Sorting

প্রব্লেম স্টেটমেন্টঃ একটি N সাইজের এরে দেয়া হবে। ম্যাক্সিমাম N  অপারেশনের মাধ্যমে এরে টিকে ইনক্রেজিং অর্ডারে সাজানো যাবে কিনা।

এরেটিকে ইনক্রেজিং অর্ডারে সাজাতে আমাদের প্রথমে তিনটি ভ্যালু  X, Y,  Z  নিতে হবে । তারপর, Y,  Z এর মানের বিয়োগফলকে X ইন্ডেক্সের ভ্যালু তে বসিয়ে দিতে হবে।

সলিউশনঃ যেহেতু মাক্সিমাম N  অপারেশন করা যাবে, সুতরাং Y  এবং Z ইন্ডেক্সের বিয়োগফলকে 0 ইনডেক্স থেকে  ইন্ডেক্সের  N - 2 পর্যন্ত সবগুলাতে বসিয়ে দিব। তারপর চেক দিবো  Y ইন্ডেক্সের ভ্যালু  Z  ইন্ডেক্সের ভ্যালু থেকে বড় কিনা। যদি বড় হয়ে তাহলে এরেটিকে ইনক্রেজিং অর্ডারে সাজানো যাবে না। আরো একটি চেক দিতে হবে লাস্ট দুই টি ইন্ডেক্সে।  যদি Y এবং Z  ইনডেক্সের বিয়োগফল ইটসেলফ Y অথবা Z ইন্ডেক্সের ভ্যালুর যেকোন একটি অথবা দুই টি থেকেই বড় হয় তাহলে এরেটিকে নন-ডিক্রেজিং বানানো যাবে না।

এছাড়া এরেটিকে নন-ডিক্রেজিং বানানো যাবে। এক্স হবে 0 ইন্ডেক্স থেকে N-2  ইন্ডেক্স পর্যন্ত। Y, Z হবে লাস্ট দুইটা ইন্ডেক্স।

 CODE:

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long
4. int32_t main(){
5. ios_base::sync_with_stdio(false);cin.tie(NULL);
6. ll T;
7. cin >> T;
8. while(T--){
9. ll n;
10. cin >> n;
11. vector<ll>v(n),S(n);
12. for(ll i = 0; i < n; ++i){ cin >> v[i]; S[i] = v[i];}
13. sort(S.begin(),S.end());
14. if(S == v) cout << 0 << '\n';
15. else if(v[n - 2] > v[ n - 1]) cout << -1 << '\n';
16. else if(v[n - 2] - v[n - 1] > v[n - 1] || v[ n - 2] - v[n - 1] > v[n - 2]) cout << -1 << '\n';
17. else{
18. cout << n - 2<< '\n';
19. for( ll i = 0; i < n - 2; ++i){
20. cout << i + 1 << ' ' << n - 1 << ' ' << n << '\n';
21. }
22. }
24. }
25. }