deadwing97

PERMLIST Tester

Feb 24th, 2019
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  19. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  20. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  21. //cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
  22.  
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25.  
  26. #define f(i,a,b) for(i=a;i<b;i++)
  27. #define rep(i,n) f(i,0,n)
  28. #define fd(i,a,b) for(i=a;i>=b;i--)
  29. #define pb push_back
  30. #define mp make_pair
  31. #define vi vector< int >
  32. #define vl vector< ll >
  33. #define ss second
  34. #define ff first
  35. #define ll long long
  36. #define pii pair< int,int >
  37. #define pll pair< ll,ll >
  38. #define sz(a) a.size()
  39. #define inf (1000*1000*1000+5)
  40. #define all(a) a.begin(),a.end()
  41. #define tri pair<int,pii>
  42. #define vii vector<pii>
  43. #define vll vector<pll>
  44. #define viii vector<tri>
  45. #define mod (1000*1000*1000+7)
  46. #define pqueue priority_queue< int >
  47. #define pdqueue priority_queue< int,vi ,greater< int > >
  48. #define flush fflush(stdout)
  49. #define primeDEN 727999983
  50. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  51.  
  52. // find_by_order()  // order_of_key
  53. typedef tree<
  54. int,
  55. null_type,
  56. less<int>,
  57. rb_tree_tag,
  58. tree_order_statistics_node_update>
  59. ordered_set;
  60.  
  61. int p[1234567];
  62. vi oper1,oper2,ord;
  63. int check(int l,int r,int st,int en){
  64.     //cout<<l<<" "<<r<<" "<<st<<" "<<en<<endl;
  65.     if(l==r){
  66.         return 1;
  67.     }
  68.     int i,j;
  69.     ll sum1,sum2,poss1,poss2,ind;
  70.     i=l;
  71.     j=r;
  72.     sum1=0;
  73.     sum2=0;
  74.     poss1=0;
  75.     poss2=0;
  76.     ind=0;
  77.     int found=0,left;
  78.     while(i<j){
  79.         sum1+=p[i];
  80.         sum2+=p[j];
  81.         poss1+=st+ind;
  82.         poss2+=en-ind;
  83.         if(poss1==sum1 || poss2==sum1){
  84.             found=1;
  85.             left=1;
  86.             break;
  87.         }
  88.         if(poss1==sum2 || poss2==sum2){
  89.             found=1;
  90.             left=0;
  91.             break;
  92.         }
  93.         ind++;
  94.         i++;
  95.         j--;
  96.     }
  97.  
  98.     if(!found)
  99.         return 0;
  100.     int val1,val2;
  101.     int gg=0;
  102.     if(left){
  103.         if(poss1==sum1){
  104.             val1=check(l,i,st,st+ind);
  105.             val2=check(i+1,r,st+ind+1,en);
  106.             gg=1;
  107.         }
  108.         else{
  109.             val1=check(l,i,en-ind,en);
  110.             val2=check(i+1,r,st,en-ind-1);
  111.             gg=2;
  112.         }
  113.     }
  114.     else{
  115.         if(poss2==sum2){
  116.             gg=1;
  117.             val1=check(l,j-1,st,en-ind-1);
  118.             val2=check(j,r,en-ind,en);
  119.         }
  120.         else{
  121.             gg=2;
  122.             val1=check(l,j-1,st+ind+1,en);
  123.             val2=check(j,r,st,st+ind);
  124.         }
  125.     }
  126.     if(val1==0 || val2==0){
  127.         return 0;
  128.     }
  129.     oper1.pb(val1);
  130.     oper2.pb(val2);
  131.     ord.pb(gg);
  132.     return (int)oper1.size()+1;
  133. }
  134.  
  135. int main(){
  136.     std::ios::sync_with_stdio(false); cin.tie(NULL);
  137.     int t;
  138.     cin>>t;
  139.     while(t--){
  140.         oper1.clear();
  141.         oper2.clear();
  142.         ord.clear();
  143.         int n;
  144.         cin>>n;
  145.         int i;
  146.         rep(i,n){
  147.             cin>>p[i];
  148.         }
  149.         if(check(0,n-1,1,n)){
  150.             //cout<<"YES"<<endl;
  151.             printf("YES\n");
  152.         }
  153.         else{
  154.             printf("NO\n");
  155.             continue;
  156.         }
  157.         //cout<<oper1.size()<<endl;
  158.         printf("%d\n",(int)oper1.size());
  159.         rep(i,oper1.size()){
  160.             //cout<<oper1[i]<<" "<<oper2[i]<<" "<<ord[i]<<endl;
  161.             printf("%d %d %d\n",oper1[i],oper2[i],ord[i]);
  162.         }
  163.     }
  164.    
  165.     return 0;  
  166. }
RAW Paste Data