96pts TLE 求调教
查看原帖
96pts TLE 求调教
416242
New_hope楼主2023/10/19 18:26

怎么 TT 了 11 个点的呀

#include<bits/stdc++.h>
#define _ (int)(1e6 + 4)
using namespace std;

int n; 
int a[_],pos[_];
deque<int> dq1,dq2;

inline void init() {
	while(!dq1.empty()) dq1.pop_front();
    while(!dq2.empty()) dq2.pop_front();
}
inline void solve() {

	init();
    int i; 
	string ah = "L", ed = "L";
    i = 2 * n; while(a[i] != a[1]) { dq1.push_front(a[i]), i --; }
    i = 2;     while(a[i] != a[1]) { dq2.push_back(a[i]), i ++; }
    
    bool L = 1, R = 1;
    while(dq1.size() || dq2.size()) {
        if(dq1.front() == dq2.front() && dq1.size() && dq2.size()) { ah += 'L', ed = 'R' + ed, dq1.pop_front(), dq2.pop_front(); }
        else if(dq2.front() == dq2.back() && dq2.size() >= 2) { ah += 'L', ed = 'L' + ed, dq2.pop_front(), dq2.pop_back(); }
        else if(dq1.front() == dq1.back() && dq1.size() >= 2) { ah += 'R', ed = 'R' + ed, dq1.pop_back(), dq1.pop_front(); }
        else if(dq1.back() == dq2.back() && dq1.size() && dq2.size()) { ah += 'R', ed = 'L' + ed, dq1.pop_back(), dq2.pop_back(); }
		else { L = 0; break; } 
    }
    if(L) { cout << ah + ed << endl; return ; }
    
   	init();
	ah = "R", ed = "L";
    i = 2 * n - 1; while(a[i] != a[2 * n]) { dq1.push_front(a[i]), i --; }
    i = 1;         while(a[i] != a[2 * n]) { dq2.push_back(a[i]), i ++; }
    
    while(dq1.size() || dq2.size()) {
        if(dq1.front() == dq2.front() && dq1.size() && dq2.size()) { ah += 'L', ed = 'R' + ed, dq1.pop_front(), dq2.pop_front(); }
        else if(dq2.front() == dq2.back() && dq2.size() >= 2) { ah += 'L', ed = 'L' + ed, dq2.pop_front(), dq2.pop_back(); }
        else if(dq1.front() == dq1.back() && dq1.size() >= 2) { ah += 'R', ed = 'R' + ed, dq1.pop_back(), dq1.pop_front(); }
        else if(dq1.back() == dq2.back() && dq1.size() && dq2.size()) { ah += 'R', ed = 'L' + ed, dq1.pop_back(), dq2.pop_back(); }
        else { R = 0; break; } 
    }
    if(R) { cout << ah + ed << endl; return ; }
    
    if(!L && !R) printf("-1\n");
    return ;
}
int main() {

    int T;
    scanf("%d",&T);
    while(T --) {
        scanf("%d",&n);
        for(int i = 1; i <= 2 * n; i ++) { scanf("%d",&a[i]); }
        solve();
    }
    return 0;
}
2023/10/19 18:26
加载中...