Submission #25515063

Source Code Expand

#include <iostream>
using namespace std;

int main() { cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n; n *= 2;
	const int maxn = int(1e6) + 10;
	static int A[maxn], B[maxn];
	for (int i=1; i<=n; ++i) cin >> A[i];
	for (int i=1; i<=n; ++i) cin >> B[i];

	const int inf = int(1e9);
	static int dp[maxn][4];
	dp[0][2] = -inf; dp[0][3] = inf;
	for (int i=1; i<=n; ++i) {
		int v[2] = {A[i], B[i]};
		for (int j=0; j<2; ++j) {
			int &dmx = dp[i][2*j], &dmn = dp[i][2*j+1];
			dmx = -inf;
			dmn = inf;
			int bv[2] = {A[i-1], B[i-1]};
			for (int bj=0; bj<2; ++bj) if (bv[bj]<=v[j]) {
				int bmx = dp[i-1][2*bj], bmn = dp[i-1][2*bj+1];
				dmx = max(dmx, bmx + j);
				dmn = min(dmn, bmn + j);
			}
		}
	}

for (int j=0; j<2; ++j) {
	int dmx = dp[n][2*j], dmn = dp[n][2*j+1];
	if (dmn <= (n/2) & (n/2) <= dmx) {
		static char ans[maxn];
		for (int ci=n, cj=j, cd=n/2;;) {
			ans[ci] = 'A'+cj;
			if (ci == 1) break;
			int cv[2] = {A[ci], B[ci]}, bv[2] = {A[ci-1], B[ci-1]};
			for (int bj=0; bj<2; ++bj) if (bv[bj] <= cv[cj]) {
				int bd = (cd - cj);
				if (dp[ci-1][2*bj+1] <= bd && bd <= dp[ci-1][2*bj]) {
					--ci;
					cj = bj;
					cd = bd;
					break;
				}
			}
		}
		cout << (ans+1) << '\n';
		return 0;
	}
}

	cout << "-1\n";
	return 0;
}

Submission Info

Submission Time
Task A - ビルの飾りつけ 4 (Building 4)
User Namnamseo
Language C++ (GCC 9.2.1)
Score 100
Code Size 1305 Byte
Status AC
Exec Time 182 ms
Memory 28020 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:31:10: warning: suggest parentheses around comparison in operand of ‘&’ [-Wparentheses]
   31 |  if (dmn <= (n/2) & (n/2) <= dmx) {
      |      ~~~~^~~~~~~~

Judge Result

Set Name Subtask 1 Subtask 2
Score / Max Score 11 / 11 89 / 89
Status
AC × 37
AC × 69
Set Name Test Cases
Subtask 1 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt
Subtask 2 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt
Case Name Status Exec Time Memory
01-01.txt AC 8 ms 3556 KiB
01-02.txt AC 2 ms 3556 KiB
01-03.txt AC 4 ms 3512 KiB
01-04.txt AC 3 ms 3608 KiB
01-05.txt AC 5 ms 3600 KiB
01-06.txt AC 5 ms 3648 KiB
01-07.txt AC 6 ms 3536 KiB
01-08.txt AC 5 ms 3544 KiB
01-09.txt AC 5 ms 3596 KiB
01-10.txt AC 8 ms 3632 KiB
01-11.txt AC 5 ms 3552 KiB
01-12.txt AC 5 ms 3648 KiB
01-13.txt AC 4 ms 3716 KiB
01-14.txt AC 4 ms 3604 KiB
01-15.txt AC 4 ms 3652 KiB
01-16.txt AC 4 ms 3736 KiB
01-17.txt AC 6 ms 3600 KiB
01-18.txt AC 4 ms 3620 KiB
01-19.txt AC 4 ms 3600 KiB
01-20.txt AC 2 ms 3712 KiB
01-21.txt AC 4 ms 3652 KiB
01-22.txt AC 4 ms 3616 KiB
01-23.txt AC 4 ms 3604 KiB
01-24.txt AC 6 ms 3620 KiB
01-25.txt AC 4 ms 3656 KiB
01-26.txt AC 3 ms 3676 KiB
01-27.txt AC 4 ms 3596 KiB
01-28.txt AC 7 ms 3588 KiB
01-29.txt AC 3 ms 3616 KiB
01-30.txt AC 4 ms 3600 KiB
01-31.txt AC 4 ms 3652 KiB
01-32.txt AC 4 ms 3580 KiB
01-33.txt AC 4 ms 3600 KiB
02-01.txt AC 169 ms 26556 KiB
02-02.txt AC 172 ms 26132 KiB
02-03.txt AC 162 ms 25820 KiB
02-04.txt AC 172 ms 26232 KiB
02-05.txt AC 164 ms 26232 KiB
02-06.txt AC 160 ms 26352 KiB
02-07.txt AC 171 ms 27904 KiB
02-08.txt AC 158 ms 26676 KiB
02-09.txt AC 176 ms 27256 KiB
02-10.txt AC 176 ms 27852 KiB
02-11.txt AC 179 ms 27952 KiB
02-12.txt AC 177 ms 27952 KiB
02-13.txt AC 170 ms 27984 KiB
02-14.txt AC 166 ms 27900 KiB
02-15.txt AC 168 ms 27984 KiB
02-16.txt AC 168 ms 27904 KiB
02-17.txt AC 182 ms 27852 KiB
02-18.txt AC 177 ms 27916 KiB
02-19.txt AC 136 ms 27988 KiB
02-20.txt AC 133 ms 27988 KiB
02-21.txt AC 126 ms 27908 KiB
02-22.txt AC 132 ms 28020 KiB
02-23.txt AC 169 ms 27920 KiB
02-24.txt AC 151 ms 27744 KiB
02-25.txt AC 150 ms 28020 KiB
02-26.txt AC 152 ms 27856 KiB
02-27.txt AC 144 ms 26452 KiB
02-28.txt AC 152 ms 28016 KiB
02-29.txt AC 152 ms 27516 KiB
02-30.txt AC 155 ms 27964 KiB
02-31.txt AC 147 ms 27084 KiB
02-32.txt AC 158 ms 27908 KiB
sample-01.txt AC 10 ms 3508 KiB
sample-02.txt AC 3 ms 3452 KiB
sample-03.txt AC 2 ms 3552 KiB
sample-04.txt AC 1 ms 3584 KiB