Submission #283502

#	Time	Username	Problem	Language	Result	Execution time	Memory
283502		ChrisT	Building 4 (JOI20_building4)	C++17	100 / 100	467 ms	48248 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e6 + 5, INF = 1e9;
int a[MN][2], dp[MN][2][2], ans[MN];
int main () {
	int n;
	scanf ("%d",&n); n*=2;
	for (int i = 1; i <= n; i++) scanf ("%d",&a[i][0]);
	for (int i = 1; i <= n; i++) scanf ("%d",&a[i][1]);
	dp[1][0][0] = dp[1][0][1] = 0;
	dp[1][1][0] = dp[1][1][1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i][0][0] = dp[i][1][0] = INF; dp[i][0][1] = dp[i][1][1] = -INF;
		for (int take = 0; take < 2; take++) {
			for (int lst = 0; lst < 2; lst++) if (a[i][take] >= a[i-1][lst]) {
				dp[i][take][0] = min(dp[i][take][0],dp[i-1][lst][0]+take);
				dp[i][take][1] = max(dp[i][take][1],dp[i-1][lst][1]+take);
			}
		}
	}
	int cur = n, take = -1, need = n/2;
	if (dp[n][0][0] <= need && need <= dp[n][0][1]) take = 0;
	else if (dp[n][1][0] <= need && need <= dp[n][1][1]) take = 1;
	if (!~take) return !printf ("-1\n");
	ans[n] = take; need -= take == 1;
	while (cur > 1) {
		if (a[cur-1][0] <= a[cur][take] && dp[cur-1][0][0] <= need && need <= dp[cur-1][0][1]) take = 0;
		else take = 1, need--;
		ans[--cur] = take;
	} 
	for (int i = 1; i <= n; i++) printf ("%c",ans[i] ? 'B' : 'A');
	printf ("\n");
	return 0;
}

Compilation message (stderr)

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

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