deadwing97

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