이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define err(x) cerr<<#x<<" : "<<x<<'\n';
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
using namespace std;
const int N=1e6+4;
int l[2][N],r[2][N],a[2][N];
bool ans[N];
int main(){
iostream::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
FOR(b,0,1) FOR(i,1,2*n) cin>>a[b][i];
FOR(b,0,1) FOR(i,1,2*n) r[b][i]=-1;
FOR(b,0,1) FOR(i,1,2*n) l[b][i]=1e9;
FOR(i,1,2*n){
FOR(b,0,1){
if(a[1][i]>=a[b][i-1]&&r[b][i-1]!=-1){ maxm(r[1][i],r[b][i-1]+1); minm(l[1][i],l[b][i-1]+1);}
}
FOR(b,0,1){
if(a[0][i]>=a[b][i-1]&&r[b][i-1]!=-1){ maxm(r[0][i],r[b][i-1]); minm(l[0][i],l[b][i-1]);}
}
}
bool last;
bool ok=0;
if(n>=l[0][2*n]&&n<=r[0][2*n]){
ok=1; ans[2*n]=0; last=0;
}
if(n>=l[1][2*n]&&n<=r[1][2*n]){
ok=1; ans[2*n]=1; last=1;
}
if(!ok){
cout<<"-1\n";
return 0;
}
int x=n-ans[2*n];
FORR(i,2*n-1,1){
if(x>=l[0][i]&&x<=r[0][i]&&a[0][i]<=a[last][i+1]){
ans[i]=0;
last=0;
}else if(x>=l[1][i]&&x<=r[1][i]&&a[1][i]<=a[last][i+1]){
ans[i]=1;
last=1;
x--;
}
}
FOR(i,1,2*n) cout<<(char)('A'+ans[i]);
cout<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |