이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N=1e6+5;
int n,a[N][2];
pii dp[N][2];
bool vis[N][2];
void calc(int i,int j)
{
if(vis[i][j]) return ;
vis[i][j]=true;
dp[i][j].fi=1e9;
dp[i][j].se=-1e9;
if(a[i][j]<=a[i+1][0])
{
calc(i+1,0);
dp[i][j].fi=min(dp[i][j].fi,dp[i+1][0].fi);
dp[i][j].se=max(dp[i][j].se,dp[i+1][0].se);
}
if(a[i][j]<=a[i+1][1])
{
calc(i+1,1);
dp[i][j].fi=min(dp[i][j].fi,dp[i+1][1].fi+1);
dp[i][j].se=max(dp[i][j].se,dp[i+1][1].se+1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
n*=2;
for(int j=0;j<2;j++)
{
for(int i=1;i<=n;i++) cin>>a[i][j];
}
vis[n][0]=true;
vis[n][1]=true;
calc(0,0);
if(dp[0][0].fi>n/2||dp[0][0].se<n/2) return cout<<-1,0;
int need=n/2;
int last=0;
for(int i=1;i<=n;i++)
{
if(a[i][0]>=a[i-1][last]&&dp[i][0].fi<=need&&dp[i][0].se>=need)
{
last=0;
cout<<"A";
}
else
{
last=1;
need--;
cout<<"B";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |