Submission #669910

#	Time	Username	Problem	Language	Result	Execution time	Memory
669910		rainboy	Building 4 (JOI20_building4)	C11	100 / 100	316 ms	45260 KiB

building4

#include <stdio.h>

#define N	1000000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static int aa[N], bb[N], lla[N], rra[N], llb[N], rrb[N];
	static char cc[N + 1];
	int n, i, k;

	scanf("%d", &n), n *= 2;
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &bb[i]);
	if (aa[0] <= bb[0])
		lla[0] = 0, rra[0] = 0, llb[0] = 0, rrb[0] = 1;
	else
		lla[0] = 0, rra[0] = 1, llb[0] = 1, rrb[0] = 1;
	for (i = 0; i + 1 < n; i++) {
		lla[i + 1] = n + 1, rra[i + 1] = -1, llb[i + 1] = n + 1, rrb[i + 1] = -1;
		if (lla[i] <= rra[i]) {
			if (aa[i] <= aa[i + 1])
				lla[i + 1] = min(lla[i + 1], lla[i]), rra[i + 1] = max(rra[i + 1], rra[i]);
			if (aa[i] <= bb[i + 1])
				llb[i + 1] = min(llb[i + 1], lla[i] + 1), rrb[i + 1] = max(rrb[i + 1], rra[i] + 1);
		}
		if (llb[i] <= rrb[i]) {
			if (bb[i] <= aa[i + 1])
				lla[i + 1] = min(lla[i + 1], llb[i]), rra[i + 1] = max(rra[i + 1], rrb[i]);
			if (bb[i] <= bb[i + 1])
				llb[i + 1] = min(llb[i + 1], llb[i] + 1), rrb[i + 1] = max(rrb[i + 1], rrb[i] + 1);
		}
		if (aa[i + 1] <= bb[i + 1])
			llb[i + 1] = min(llb[i + 1], lla[i + 1]), rrb[i + 1] = max(rrb[i + 1], rra[i + 1]);
		else
			lla[i + 1] = min(lla[i + 1], llb[i + 1]), rra[i + 1] = max(rra[i + 1], rrb[i + 1]);
	}
	k = n / 2;
	if (!(lla[n - 1] <= k && k <= rra[n - 1] || llb[n - 1] <= k && k <= rrb[n - 1])) {
		printf("-1\n");
		return 0;
	}
	for (i = n - 1; i >= 0; i--)
		if (aa[i] <= bb[i]) {
			if (lla[i] <= k && k <= rra[i] && (i + 1 == n || aa[i] <= (cc[i + 1] == 'A' ? aa[i + 1] : bb[i + 1])))
				cc[i] = 'A';
			else
				cc[i] = 'B', k--;
		} else {
			if (llb[i] <= k && k <= rrb[i] && (i + 1 == n || bb[i] <= (cc[i + 1] == 'A' ? aa[i + 1] : bb[i + 1])))
				cc[i] = 'B', k--;
			else
				cc[i] = 'A';
		}
	printf("%s\n", cc);
	return 0;
}

Compilation message (stderr)

building4.c: In function 'main':
building4.c:42:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |  if (!(lla[n - 1] <= k && k <= rra[n - 1] || llb[n - 1] <= k && k <= rrb[n - 1])) {
      |        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
building4.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d", &n), n *= 2;
      |  ^~~~~~~~~~~~~~~
building4.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
building4.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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