Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define LOCAL
- #include <bits/stdc++.h>
- using namespace std;
- vector <int> a;
- vector <char> k, ans;
- //set <pair<int, pair <bool, bool>>> test;
- /*
- int pr(int p, int l, int r){
- return a[l] > a[p] + a[r] > a[p];
- }
- */
- void func(int p, int l, int r){
- //cerr << p << " " << l << " " << r << endl;
- /*pair <int, pair <bool, bool>> t;
- t = {p, {a[l] > a[p], a[r] > a[p]}};
- if(test.find(t) != test.end()){
- //cerr << "ret" << endl;
- return;
- }
- test.insert(t);
- */
- if(a[l] > a[p] && (a[l] <= a[r] || a[r] <= a[p])){
- k.push_back('L');
- if(k.size() > ans.size())
- ans = k;
- if(r-l >= 1)
- func(l, l+1, r);
- k.pop_back();
- }
- if(a[r] > a[p] && (a[r] <= a[l] || a[l] <= a[p])){
- k.push_back('R');
- if(k.size() > ans.size())
- ans = k;
- if(r-l >= 1)
- func(r, l, r-1);
- k.pop_back();
- }
- ////cerr << endl;
- }
- void solve(){
- a.clear();
- ans.clear();
- k.clear();
- //test.clear();
- int n;
- cin >> n;
- for(int i = 0; i < n; i++){
- int c;
- cin >> c;
- a.push_back(c);
- }
- k.push_back('L');
- if(k.size() > ans.size())
- ans = k;
- func(0, 1, a.size() -1);
- k.pop_back();
- k.push_back('R');
- func(a.size()-1, 0, a.size()-2);
- k.pop_back();
- cout << ans.size() << endl;;
- for(int i = 0; i < ans.size(); i++)
- cout << ans[i];
- cout << endl << endl;
- //cerr << endl;
- }
- void test(){
- vector <char> o;
- for(int i = 0; i < pow(2, 17); i++)
- o.push_back('A');
- //cerr << "good" << endl;
- }
- int main(){
- test();
- ios_base::sync_with_stdio(0);
- cin.tie();
- cout.tie();
- int n = 1;
- #ifdef LOCAL
- freopen("in.data", "r", stdin);
- freopen("out.data", "w", stdout);
- freopen("test.data", "w", stderr);
- cin >> n;
- #endif
- while(n--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement