Submission #212054

#	Time	Username	Problem	Language	Result	Execution time	Memory
212054		Just_Solve_The_Problem	Building 4 (JOI20_building4)	C++11	100 / 100	423 ms	26220 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define fr first
#define sc second

const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;

int a[N + N], b[N + N];
int n;
pair <int, int> dp[N + N][2];

main() {
  scanf("%d", &n);
  for (int i = 1; i <= n + n; i++) {
  	scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n + n; i++) {
  	scanf("%d", &b[i]);
  }
  dp[1][0] = {1, 1};
	dp[1][1] = {0, 0};
	for (int i = 2; i <= n + n; i++) {
		int l, r;
		l = inf;
		r = 0;
		if (a[i - 1] <= a[i]) {
			l = min(l, dp[i - 1][0].fr + 1);
			r = max(r, dp[i - 1][0].sc + 1);
		}
		if (b[i - 1] <= a[i]) {   
			l = min(l, dp[i - 1][1].fr + 1);
			r = max(r, dp[i - 1][1].sc + 1);
		}
		dp[i][0] = {l, r};
		l = inf;
		r = 0;
		if (a[i - 1] <= b[i]) {
			l = min(l, dp[i - 1][0].fr);
			r = max(r, dp[i - 1][0].sc);
		}
		if (b[i - 1] <= b[i]) {
			l = min(l, dp[i - 1][1].fr);
			r = max(r, dp[i - 1][1].sc);
		}
		dp[i][1] = {l, r};
	}
	/*
	for (int i = 1; i <= n + n; i++) {
		cout << dp[i][0].fr << ' ' << dp[i][0].sc << ' ' << dp[i][1].fr << ' ' << dp[i][1].sc << '\n';
	}
	*/
	int lst = -1;
	if (dp[n + n][0].fr <= n && n <= dp[n + n][0].sc) {
		lst = 0;
	}
	if (dp[n + n][1].fr <= n && n <= dp[n + n][1].sc) {
		lst = 1;
	}
	if (lst == -1) {
		cout << lst;
		return 0;
	}
	int cur = n;
	string ans;
	int val = inf;
	for (int i = n + n; i >= 1; i--) {
		if (dp[i][lst].fr <= cur && cur <= dp[i][lst].sc && ((lst == 0) ? a[i] : b[i]) <= val) {
			ans.push_back(lst + 'A');
		} else {
			lst ^= 1;
			ans.push_back(lst + 'A');
		}
		val = (lst == 0) ? a[i] : b[i];
		cur -= (lst == 0);
	} 
	reverse(ans.begin(), ans.end());
	cout << ans << '\n';
}

Compilation message (stderr)

building4.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
building4.cpp: In function 'int main()':
building4.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
building4.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i]);
    ~~~~~^~~~~~~~~~~~~
building4.cpp:21:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b[i]);
    ~~~~~^~~~~~~~~~~~~

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