This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
const int INF = 1e9;
int N;
int A[1'000'000], B[1'000'000];
// A の数を最大化
int dpA[1'000'000][2];
int solveA(int n, int l){
if(n == 2*N) return 0;
if(n == 0) return max(solveA(1, 0)+1, solveA(1, 1));
if(dpA[n][l] != -1) return dpA[n][l];
int ret = -INF;
if(l == 0){
if(A[n-1] <= A[n]) ret = max(ret, solveA(n+1, 0)+1);
if(A[n-1] <= B[n]) ret = max(ret, solveA(n+1, 1));
}
else{
if(B[n-1] <= A[n]) ret = max(ret, solveA(n+1, 0)+1);
if(B[n-1] <= B[n]) ret = max(ret, solveA(n+1, 1));
}
return dpA[n][l] = ret;
}
// B の数を最大化
int dpB[1'000'000][2];
int solveB(int n, int l){
if(n == 2*N) return 0;
if(n == 0) return max(solveB(1, 0), solveB(1, 1)+1);
if(dpB[n][l] != -1) return dpB[n][l];
int ret = -INF;
if(l == 0){
if(A[n-1] <= A[n]) ret = max(ret, solveB(n+1, 0));
if(A[n-1] <= B[n]) ret = max(ret, solveB(n+1, 1)+1);
}
else{
if(B[n-1] <= A[n]) ret = max(ret, solveB(n+1, 0));
if(B[n-1] <= B[n]) ret = max(ret, solveB(n+1, 1)+1);
}
return dpB[n][l] = ret;
}
void print(int n, int a, int l){
if(l == 0) printf("A");
if(l == 1) printf("B");
if(n == 2*N) return;
if(n == 0){
if(solveA(1, 0) >= N-1 && solveB(1, 0) >= N){
print(n+1, a+1, 0);
return;
}
if(solveA(1, 1) >= N && solveB(1, 1) >= N-1){
print(n+1, a, 1);
return;
}
}
int b = n-a;
if(l == 0){
if(A[n-1] <= A[n] && solveA(n+1, 0) >= N-a-1 && solveB(n+1, 0) >= N-b){
print(n+1, a+1, 0);
return;
}
if(A[n-1] <= B[n] && solveA(n+1, 1) >= N-a && solveB(n+1, 1) >= N-b-1){
print(n+1, a, 1);
return;
}
}
else{
if(B[n-1] <= A[n] && solveA(n+1, 0) >= N-a-1 && solveB(n+1, 0) >= N-b){
print(n+1, a+1, 0);
return;
}
if(B[n-1] <= B[n] && solveA(n+1, 1) >= N-a && solveB(n+1, 1) >= N-b-1){
print(n+1, a, 1);
return;
}
}
}
signed main(){
scanf("%d", &N);
rep(i, 2*N) scanf("%d", A+i);
rep(i, 2*N) scanf("%d", B+i);
memset(dpA, -1, sizeof(dpA));
memset(dpB, -1, sizeof(dpB));
if(solveA(0, -1) < N || solveB(0, -1) < N){
printf("-1\n");
return 0;
}
print(0, 0, -1);
printf("\n");
}
Compilation message (stderr)
building4.cpp: In function 'int main()':
building4.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
| ^
building4.cpp:95:2: note: in expansion of macro 'rep'
95 | rep(i, 2*N) scanf("%d", A+i);
| ^~~
building4.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
| ^
building4.cpp:96:2: note: in expansion of macro 'rep'
96 | rep(i, 2*N) scanf("%d", B+i);
| ^~~
building4.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
building4.cpp:95:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | rep(i, 2*N) scanf("%d", A+i);
| ~~~~~^~~~~~~~~~~
building4.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | rep(i, 2*N) scanf("%d", B+i);
| ~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |