Advertisement
Guest User

Untitled

a guest
Apr 26th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #define LOCAL
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. vector <int> a;
  7. vector <char> k, ans;
  8. //set <pair<int, pair <bool, bool>>> test;
  9. /*
  10. int pr(int p, int l, int r){
  11.     return a[l] > a[p] + a[r] > a[p];
  12. }
  13. */
  14. void func(int p, int l, int r){
  15.     //cerr << p << " " << l << " " << r << endl;
  16.     /*pair <int, pair <bool, bool>> t;
  17.  
  18.     t = {p, {a[l] > a[p], a[r] > a[p]}};
  19.     if(test.find(t) != test.end()){
  20.         //cerr << "ret" << endl;
  21.         return;
  22.     }
  23.     test.insert(t);
  24. */
  25.     if(a[l] > a[p] && (a[l] <= a[r] || a[r] <= a[p])){
  26.         k.push_back('L');
  27.         if(k.size() > ans.size())
  28.             ans = k;
  29.  
  30.         if(r-l >= 1)
  31.             func(l, l+1, r);
  32.         k.pop_back();
  33.     }
  34.  
  35.     if(a[r] > a[p] && (a[r] <= a[l] || a[l] <= a[p])){
  36.         k.push_back('R');
  37.  
  38.         if(k.size() > ans.size())
  39.             ans = k;
  40.  
  41.         if(r-l >= 1)
  42.             func(r, l, r-1);
  43.         k.pop_back();
  44.     }
  45.     ////cerr << endl;
  46.  
  47. }
  48.  
  49. void solve(){
  50.     a.clear();
  51.     ans.clear();
  52.     k.clear();
  53.     //test.clear();
  54.  
  55.     int n;
  56.     cin >> n;
  57.     for(int i = 0; i < n; i++){
  58.         int c;
  59.         cin >> c;
  60.         a.push_back(c);
  61.     }
  62.  
  63.     k.push_back('L');
  64.     if(k.size() > ans.size())
  65.             ans = k;
  66.     func(0, 1, a.size() -1);
  67.     k.pop_back();
  68.  
  69.     k.push_back('R');
  70.     func(a.size()-1, 0, a.size()-2);
  71.     k.pop_back();
  72.  
  73.     cout << ans.size() << endl;;
  74.     for(int i = 0; i < ans.size(); i++)
  75.         cout << ans[i];
  76.     cout << endl << endl;
  77.     //cerr << endl;
  78. }
  79.  
  80. void test(){
  81.     vector <char> o;
  82.     for(int i = 0; i < pow(2, 17); i++)
  83.         o.push_back('A');
  84.     //cerr << "good" << endl;
  85. }
  86.  
  87. int main(){
  88.     test();
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie();
  91.     cout.tie();
  92.  
  93.     int n = 1;
  94. #ifdef LOCAL
  95.     freopen("in.data", "r", stdin);
  96.     freopen("out.data", "w", stdout);
  97.     freopen("test.data", "w", stderr);
  98.     cin >> n;
  99. #endif
  100.  
  101.     while(n--)
  102.         solve();
  103.  
  104. return 0;  
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement