Submission #220223

#	Time	Username	Problem	Language	Result	Execution time	Memory
220223		atoiz	Building 4 (JOI20_building4)	C++14	100 / 100	388 ms	47356 KiB

building4

/*input
6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <cassert>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <chrono>
#include <utility>
#include <fstream>

using namespace std;

// #define LOCAL
#define endl '\n'

#define deb err_stream()
struct err_stream
{
	template <typename T>
	err_stream& operator<< (T x)
	{
		#ifdef LOCAL
		cout << x << flush;
		#endif
		return *this;
	}
};

using ll = int64_t;
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
#define SZ(a) ((int) a.size())
#define ALL(a) begin(a), end(a)

mt19937 rng(chrono::system_clock().now().time_since_epoch().count());

const int MAXN = 1000007, INF = 1e9 + 7;
int N, A[MAXN][2], L[MAXN][2], R[MAXN][2];
bool ok[MAXN][2], ans[MAXN];

void trace(int i, int k, int x)
{
	if (i == 0) return;
	assert(ok[i][k]);
	ans[i] = k;

	x -= k;
	FOR(j, 0, 1) if (ok[i - 1][j] && A[i - 1][j] <= A[i][k] && L[i - 1][j] <= x && x <= R[i - 1][j]) {
		trace(i - 1, j, x);
		return;
	}
	assert(0);
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	N <<= 1;
	FOR(i, 1, N) cin >> A[i][0];
	FOR(i, 1, N) cin >> A[i][1];

	ok[0][0] = ok[0][1] = 1; A[N + 1][0] = INF;
	FOR(i, 1, N + 1) FOR(k, 0, 1) FOR(j, 0, 1) {
		if (ok[i - 1][j] && A[i - 1][j] <= A[i][k]) {
			if (!ok[i][k]) {
				ok[i][k] = 1;
				L[i][k] = L[i - 1][j] + k;
				R[i][k] = R[i - 1][j] + k;
			} else {
				// assert(R[i][k] >= L[i - 1][j] + k - 1);
				// assert(L[i][k] <= R[i - 1][j] + k + 1);
				L[i][k] = min(L[i][k], L[i - 1][j] + k);
				R[i][k] = max(R[i][k], R[i - 1][j] + k);
			}
		}
	}

	if (!ok[N + 1][0] || N / 2 < L[N + 1][0] || R[N + 1][0] < N / 2) cout << -1 << endl;
	else {
		trace(N + 1, 0, N / 2);
		FOR(i, 1, N) cout << (ans[i] ? 'B' : 'A');
		cout << endl;
	}

	deb << "Execution time: " << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

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