Submission #859793

#	Time	Username	Problem	Language	Result	Execution time	Memory
859793		serifefedartar	건물 4 (JOI20_building4)	C++17	11 / 100	2049 ms	24956 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 22; 
const ll MAXN = 1e6 + 5;

int A[MAXN], B[MAXN];
pair<int,int> dp[MAXN][2];

int main() {
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= 2*N; i++)
		scanf("%d", A + i);
	for (int i = 1; i <= 2*N; i++)
		scanf("%d", B + i);

	for (int i = 0; i < MAXN; i++)
		dp[i][0] = dp[i][1] = {2*N+2, 0};
	dp[0][0] = dp[0][1] = {0, 0};

	for (int i = 1; i <= 2*N; i++) {
		if (A[i-1] <= A[i])
			dp[i][0] = {min(dp[i][0].f, dp[i-1][0].f + 1), max(dp[i][0].s, dp[i-1][0].s + 1)};
		if (A[i-1] <= B[i])
			dp[i][1] = {min(dp[i][1].f, dp[i-1][0].f), max(dp[i][1].s, dp[i-1][0].s)};
		if (B[i-1] <= A[i])
			dp[i][0] = {min(dp[i][0].f, dp[i-1][1].f + 1), max(dp[i][0].s, dp[i-1][1].s + 1)};
		if (B[i-1] <= B[i])
			dp[i][1] = {min(dp[i][1].f, dp[i-1][1].f), max(dp[i][1].s, dp[i-1][1].s)};
	}

	int last = -1;
	if (dp[2*N][0].f <= N && N <= dp[2*N][0].s)
		last = 0;
	else if (dp[2*N][1].f <= N && N <= dp[2*N][1].s)
		last = 1;

	if (last == -1) {
		cout << "-1\n";
		return 0;
	}

	string ans;
	ans = ans + (last == 0 ? "A" : "B");
	int now = N - (last == 0);
	for (int i = 2*N - 1; i >= 1; i--) {
		if (dp[i][0].f <= now && now <= dp[i][0].s && A[i] <= (last == 0 ? A[i+1] : B[i+1]))
			last = 0;
		else if (dp[i][1].f <= now && now <= dp[i][1].s)
			last = 1;

		now = now - (last == 0);
		ans = ans + (last == 0 ? "A" : "B");
	}

	reverse(ans.begin(), ans.end());
	cout << ans << "\n";
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
building4.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
building4.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d", B + i);
      |   ~~~~~^~~~~~~~~~~~~

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