제출 #414914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414914		Pro_ktmr	건물 4 (JOI20_building4)	C++17	100 / 100	562 ms	90248 KiB

building4

#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");
}

컴파일 시 표준 에러 (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);
      |              ~~~~~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89