fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Speed
  5. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6.  
  7. // Typedefs
  8. #define int long long
  9. #define rep(i,a,b) for(int i=a;i<b;++i)
  10. #define endl '\n'
  11.  
  12. // Consts
  13. const int N = 2e5 + 5;
  14.  
  15. // Check if array is good
  16. bool isGood(int a[], int n, int &x) {
  17.     for (int i = 0; i <= n - 5; ++i) {
  18.         if (a[i] < a[i+1] && a[i+1] < a[i+2] && a[i+2] < a[i+3] && a[i+3] < a[i+4]) {
  19.             x = i;
  20.             return false;
  21.         }
  22.         if (a[i] > a[i+1] && a[i+1] > a[i+2] && a[i+2] > a[i+3] && a[i+3] > a[i+4]) {
  23.             x = i;
  24.             return false;
  25.         }
  26.     }
  27.     return true;
  28. }
  29.  
  30. // Main logic
  31. void solve() {
  32.     int n;
  33.     cin >> n;
  34.     int a[N];
  35.     rep(i, 0, n) cin >> a[i];
  36.  
  37.     int l = 0, r = n - 1;
  38.     int res_ptr = 0;
  39.     char res[N]; // to store 'L' and 'R'
  40.  
  41.     int temp[N]; // simulated remaining array
  42.     int len;
  43.  
  44.     while (l <= r) {
  45.         len = 0;
  46.         for (int i = l; i <= r; ++i)
  47.             temp[len++] = a[i];
  48.  
  49.         int x = -1;
  50.         if (isGood(temp, len, x)) {
  51.             res[res_ptr++] = 'L';
  52.             l++;
  53.         } else {
  54.             // Inject LLRLR
  55.             res[res_ptr++] = 'L';
  56.             res[res_ptr++] = 'L';
  57.             res[res_ptr++] = 'R';
  58.             res[res_ptr++] = 'L';
  59.             res[res_ptr++] = 'R';
  60.  
  61.             l += 3;
  62.             r -= 2;
  63.         }
  64.     }
  65.  
  66.     // Output result
  67.     rep(i, 0, res_ptr) cout << res[i];
  68.     cout << endl;
  69. }
  70.  
  71. // Driver
  72. int32_t main() {
  73.     fast_io;
  74.     int t;
  75.     cin >> t;
  76.     while (t--) solve();
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
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 
LLRLRLL
LLRLRLLLL
LLLLLLLLLLLL
LLLLLL
LLLLL
LLLLLLLLL
https://ideone.com/HxzuvQ
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!