이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Cookie197
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<int,int>
#define pdd pair<double ,double>
#define mp make_pair
//#define mod 998244353
#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl;
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << " second = " << x.second << endl
int a[1000006], b[1000006], arr[1000006][2];
int n;
//bool ok[1000005][2];
//int dpx[1000005][2], dpy[1000005][2];
//char pre[1000005][2];
pii dp[1000005][2];
void ch(int &x,int y,int z,int i,int j){
//if (y<0) y = 2e9;
//if (z<0) z = 2e9;
//x = min(x,min(y,z));
//if (y==z && y==2e9) return;
//if (y<z) pre[i][j] = 'A';
//else pre[i][j] = 'B';
}
signed main(){
Why_does_competitive_programming_even_exist;
cin>>n;
for (int i=1;i<=2*n;i++) cin>>a[i], arr[i][0] = a[i];
for (int i=1;i<=2*n;i++) cin>>b[i], arr[i][1] = b[i];
//ok[1][0] = ok[1][1] = true;
dp[1][0] = mp(1,1), dp[1][1] = mp(0,0);
for (int i=2;i<=n*2;i++) dp[i][0] = mp(2e9,-1);
for (int i=2;i<=n*2;i++){
int x=2e9, y=2e9;
if (a[i-1] <= a[i]) x = dp[i-1][0].first;
if (b[i-1] <= a[i]) y = dp[i-1][1].first;
dp[i][0].first = min(x,y) + 1;
x = -2e9, y = -2e9;
if (a[i-1] <= a[i]) x = dp[i-1][0].second;
if (b[i-1] <= a[i]) y = dp[i-1][1].second;
dp[i][0].second = max(x,y) + 1;
x=2e9, y=2e9;
if (a[i-1] <= b[i]) x = dp[i-1][0].first;
if (b[i-1] <= b[i]) y = dp[i-1][1].first;
dp[i][1].first = min(x,y);
x = -2e9, y = -2e9;
if (a[i-1] <= b[i]) x = dp[i-1][0].second;
if (b[i-1] <= b[i]) y = dp[i-1][1].second;
dp[i][1].second = max(x,y);
//outp(dp[i][0]); outp(dp[i][1]);
}
int pos = -1, now = n;
if (dp[n*2][0].first <= n && n <= dp[n*2][0].second) pos = 0;
else if (dp[n*2][1].first <= n && n <= dp[n*2][1].second) pos = 1;
if (pos == -1){
cout<<-1<<endl;
return 0;
}
string ans = "";
for (int i=n*2;i>=1;i--){
ans += (pos==0 ? 'A' : 'B');
now -= (pos==0 ? 1 : 0);
if (arr[i-1][0] <= arr[i][pos] && dp[i-1][0].first <= now && now <= dp[i-1][0].second) pos = 0;
else if (arr[i-1][1] <= arr[i][pos] && dp[i-1][1].first <= now && now <= dp[i-1][1].second) pos = 1;
}
reverse(ans.begin(),ans.end());
cout<<ans<<endl;
/*dpx[1][0] = 1; dpy[1][1] = 1;
for (int i=1;i<2*n;i++){
if (ok[i][0] && a[i] <= a[i+1]){
ch(dpx[i+1][0], dpx[i][0] + 1, -(dpy[i][0] - 1), i+1, 0);
ch(dpy[i+1][0], dpy[i][0] - 1, -(dpx[i][0] + 1), i+1, 0);
ok[i+1][0] = true;
}
if (ok[i][1] && b[i] <= a[i+1]){
ch(dpx[i+1][0], dpx[i][1] + 1, -(dpy[i][1] - 1), i+1, 0);
ch(dpy[i+1][0], dpy[i][1] - 1, -(dpx[i][1] + 1), i+1, 0);
ok[i+1][0] = true;
}
if (ok[i][0] && a[i] <= b[i+1]){
ch(dpx[i+1][1], dpx[i][0] - 1, -(dpy[i][0] + 1), i+1, 1);
ch(dpy[i+1][1], dpy[i][0] + 1, -(dpx[i][0] - 1), i+1, 1);
ok[i+1][1] = true;
}
if (ok[i][1] && b[i] <= b[i+1]){
ch(dpx[i+1][1], dpx[i][1] - 1, -(dpy[i][1] + 1), i+1, 1);
ch(dpy[i+1][1], dpy[i][1] + 1, -(dpx[i][1] - 1), i+1, 1);
ok[i+1][1] = true;
}
}
for (int i=1;i<=n*2;i++){
cout<<dpx[i][0]<<" "<<dpx[i][1]<<" "<<dpy[i][0]<<" "<<dpy[i][1]<<endl;
}
//return 0;
if (ok[2*n][0] == false && ok[2*n][1] == false) {
cout<<-1<<endl;
return 0;
}
if (dpx[2*n][0] != 0 && dpx[2*n][1] != 0 && dpy[2*n][0] != 0 && dpy[2*n][1] != 0) {
cout<<-1<<endl;
return 0;
}
string ans = "";
int pos;
if (ok[n][0]) ans += 'A', pos = 0;
else ans += 'B', pos = 1;
for (int i=2*n;i>=2;i--){
ans += pre[i][pos];
if (pre[i][pos]=='A') pos = 0;
else pos = 1;
}
reverse(ans.begin(),ans.end());
cout<<ans<<endl;*/
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |