# PERMLIST Editorialist

Feb 24th, 2019
226
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. const int MX = (1<<20);
6.
7. int T , n;
8.
9. int arr[MX];
10.
11. vector < pair < int , pair < int , int > > > sol;
12.
13. bool nosol = 0;
14.
15. int solve(int l , int r , int dec){
16.
17.     if(l == r) return 1;
18.
19.     int lmn = (1<<30) , lmx = -1;
20.
21.     int rmn = (1<<30) , rmx = -1;
22.
23.     int mxv = r - l + 1;
24.
25.     for(int it1 = l , it2 = r , counter = 0 ; counter < (r - l + 2)/2 && !nosol && it1 < r && it2 > l ; it1++ , it2--){
26.
27.         lmn = min(lmn , arr[it1] - dec);
28.         lmx = max(lmx , arr[it1] - dec);
29.
30.         rmn = min(rmn , arr[it2] - dec);
31.         rmx = max(rmx , arr[it2] - dec);
32.
33.         if(lmn == 1 && lmx - lmn == it1 - l)
34.             sol.push_back({1 , {solve(l , it1 , dec) , solve(it1 + 1 , r , dec + it1 - l + 1)}});
35.
36.         else if(rmn == 1 && rmx - rmn == r - it2)
37.             sol.push_back({2 , {solve(l , it2 - 1 , dec + r - it2 + 1) , solve(it2 , r , dec)}});
38.
39.         else if(lmx == mxv && lmx - lmn == it1 - l)
40.             sol.push_back({2 , {solve(l , it1 , dec + r - it1) , solve(it1 + 1 , r , dec)}});
41.
42.         else if(rmx == mxv && rmx - rmn == r - it2)
43.             sol.push_back({1 , { solve(l , it2 - 1 , dec) , solve(it2 , r , dec + it2 - l) }});
44.
45.         else continue;
46.
47.         return 1 + sol.size();
48.
49.     }
50.
51.     nosol = 1;
52.
53.     return 0;
54. }
55. int main(){
56.
57.     scanf("%d",&T);
58.
59.     while(T--){
60.
61.         scanf("%d",&n);
62.
63.         for(int j = 1 ; j <= n ; j++)
64.             scanf("%d",&arr[j]);
65.
66.         sol.clear();
67.
68.         nosol = 0;
69.
70.         solve(1,n,0);
71.
72.         if(nosol) puts("NO");
73.         else{
74.             puts("YES");
75.             cout<<sol.size()<<endl;
76.             for(auto pp : sol)
77.                 printf("%d %d %d\n",pp.second.first,pp.second.second,pp.first);
78.         }
79.     }
80.
81.
82.
83. }
RAW Paste Data