fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  5. #define int long long
  6. #define pb push_back
  7. #define ff first
  8. #define ss second
  9. #define all(x) (x).begin(), (x).end()
  10. #define rall(x) (x).rbegin(), (x).rend()
  11. #define sz(x) ((int)(x).size())
  12. #define endl '\n'
  13. #define yes cout << "yes\n"
  14. #define no cout << "no\n"
  15. #define rep(i,a,b) for(int i=a;i<b;++i)
  16. #define per(i,a,b) for(int i=b-1;i>=a;--i)
  17. #define each(x,a) for(auto &x:a)
  18.  
  19. const int INF = 1e18;
  20. const int MOD = 1e9+7;
  21.  
  22. // BAD sequence checker
  23. bool isBad(int* q, int len) {
  24.     if (len < 5) return false;
  25.     for (int i = len - 5; i >= 0; --i) {
  26.         bool inc = 1, dec = 1;
  27.         rep(j, 0, 4) {
  28.             if (q[i + j] >= q[i + j + 1]) inc = 0;
  29.             if (q[i + j] <= q[i + j + 1]) dec = 0;
  30.         }
  31.         if (inc || dec) return true;
  32.     }
  33.     return false;
  34. }
  35.  
  36. void solve() {
  37.     int n;
  38.     cin >> n;
  39.     int* a = new int[n];
  40.     rep(i, 0, n) cin >> a[i];
  41.  
  42.     int* q = new int[n];
  43.     int l = 0, r = n - 1, len = 0;
  44.     string res = "";
  45.  
  46.     while (l <= r) {
  47.         bool canLeft = false, canRight = false;
  48.  
  49.         q[len] = a[l];
  50.         if (!isBad(q, len + 1)) canLeft = true;
  51.  
  52.         q[len] = a[r];
  53.         if (!isBad(q, len + 1)) canRight = true;
  54.  
  55.         if (canLeft && (!canRight || a[l] < a[r])) {
  56.             q[len++] = a[l++];
  57.             res += 'L';
  58.         } else if (canRight) {
  59.             q[len++] = a[r--];
  60.             res += 'R';
  61.         } else {
  62.             // fallback, always possible as permutation doesn't force a bad seq
  63.             q[len++] = a[l++];
  64.             res += 'L';
  65.         }
  66.     }
  67.  
  68.     cout << res << endl;
  69.  
  70.     delete[] a;
  71.     delete[] q;
  72. }
  73.  
  74. int32_t main() {
  75.     fast_io;
  76.     int t;
  77.     cin >> t;
  78.     while (t--) solve();
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6
7
1 2 3 4 5 6 7
9
1 3 6 8 9 7 5 4 2
12
1 2 11 3 6 4 7 8 12 5 10 9
6
4 1 2 5 6 3
5
1 2 3 5 4
9
5 1 8 6 2 7 9 4 3
stdout
copy 
LLLLLLL
LRLRLLLLL
LLRRRLLLLLLR
RLLLLR
LLLRL
RRLLLLLLR
https://ideone.com/c2gEHw
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!