Submission #670247

#	Time	Username	Problem	Language	Result	Execution time	Memory
670247		flappybird	Building 4 (JOI20_building4)	C++17	100 / 100	287 ms	46848 KiB

building4

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010100
#define MAXS 17
#define INF 10000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
pii operator+(pii p1, pii p2) {
	if (!~p1.first) return p2;
	if (!~p2.first) return p1;
	return pii(min(p1.first, p2.first), max(p1.second, p2.second));
}
void operator+=(pii& p1, pii p2) { p1 = p1 + p2; }
pii operator+(pii p1, int x) {
	if (!~p1.first) return p1;
	return pii(p1.first + x, p1.second + x);
}
void operator+=(pii& p1, int x) { p1 = p1 + x; }
bool ison(pii p, int x) { return p.first <= x && x <= p.second; }
pii dp[2][MAX];
int arr[2][MAX];
int ans[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	for (i = 1; i <= N * 2; i++) cin >> arr[0][i];
	for (i = 1; i <= N * 2; i++) cin >> arr[1][i];
	for (i = 1; i <= N * 2; i++) dp[0][i] = dp[1][i] = pii(-1, -1);
	dp[0][0] = pii(-1, N * 2);
	dp[1][0] = pii(-1, N * 2);
	dp[0][1] = pii(0, 0);
	dp[1][1] = pii(1, 1);
	for (i = 2; i <= N * 2; i++) for (auto c : { 0, 1 }) for (auto p : { 0, 1 }) if (arr[p][i - 1] <= arr[c][i]) dp[c][i] += dp[p][i - 1] + c;
	auto resintv = dp[0][N * 2] + dp[1][N * 2];
	if (!ison(resintv, N)) {
		cout << -1 << ln;
		return 0;
	}
	int pv = 1e9 + 10;
	int rem = N;
	for (i = N * 2; i >= 1; i--) {
		int c;
		for (c = 0; c < 2; c++) {
			if (arr[c][i] > pv) continue;
			int chk = 0;
			for (auto p : { 0, 1 }) if (((i - 1) >= (rem - c)) && arr[p][i - 1] <= arr[c][i] && ison(dp[p][i - 1], rem - c)) chk = 1;
			if (chk) break;
		}
		pv = arr[c][i];
		ans[i] = c;
		rem -= c;
	}
	for (i = 1; i <= N * 2; i++) cout << (!ans[i] ? 'A' : 'B');
}

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