Submission #228341

#	Time	Username	Problem	Language	Result	Execution time	Memory
228341		wilwxk	Building 4 (JOI20_building4)	C++14	11 / 100	117 ms	13432 KiB

building4

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5+5;
int h[MAXN][2];
int dp[MAXN][2][2];
int ans[MAXN];
int n;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n*2; i++) scanf("%d", &h[i][0]); 
	for(int i = 1; i <= n*2; i++) scanf("%d", &h[i][1]); 

	for(int i = 1; i <= n*2; i++) {
		for(int b = 0; b < 2; b++) {
			dp[i][b][0] = MAXN;
			dp[i][b][1] = -MAXN;
			for(int a = 0; a < 2; a++) {
				if(h[i-1][a] > h[i][b]) continue;
				dp[i][b][0] = min(dp[i][b][0], dp[i-1][a][0]+b);
				dp[i][b][1] = max(dp[i][b][1], dp[i-1][a][1]+b);
			}
		}
		// printf("%d > %d %d\n", i, dp[i][0][0], dp[i][0][1]);
		// printf("%d > %d %d\n", i, dp[i][1][0], dp[i][1][1]);
	}

	h[n*2+1][0] = h[n*2+1][1] = 1e9+9;

	int cnt = 0; int last = 0;
	for(int i = n*2; i >= 1; i--) {
		if(h[i][0] <= h[i+1][last]) {
			if(dp[i][0][0] <= n-cnt && dp[i][0][1] >= n-cnt) {
				ans[i] = 0;
				last = 0;
				continue;
			}
		}
		if(h[i][1] <= h[i+1][last]) {
			if(dp[i][1][0] <= n-cnt && dp[i][1][1] >= n-cnt) {
				ans[i] = 1;
				cnt++;
				last = 1;
				continue;
			}
		}
		printf("-1\n");
		return 0;
	}

	for(int i = 1; i <= n*2; i++) printf("%c", 'A'+ans[i]);
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building4.cpp:12:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n*2; i++) scanf("%d", &h[i][0]); 
                                ~~~~~^~~~~~~~~~~~~~~~
building4.cpp:13:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n*2; i++) scanf("%d", &h[i][1]); 
                                ~~~~~^~~~~~~~~~~~~~~~

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