Submission #211604

#	Time	Username	Problem	Language	Result	Execution time	Memory
211604		mieszko11b	Building 4 (JOI20_building4)	C++14	100 / 100	424 ms	26128 KiB

building4

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int n;
ii dp[1000007][2];
int a[1000007], b[1000007];

ii merge(ii a, ii b) {
	return {min(a.X, b.X), max(a.Y, b.Y)};
}

ii addone(ii a) {
	return {a.X + 1, a.Y + 1};
}

int main() {
	scanf("%d", &n);
	n *= 2;
	for(int i = 1 ; i <= n ; i++)
		scanf("%d", &a[i]);
	for(int i = 1 ; i <= n ; i++)
		scanf("%d", &b[i]);
		
	dp[1][0] = {1, 1};
	dp[1][1] = {0, 0};
	for(int i = 2 ; i <= n ; i++) {
		dp[i][0] = dp[i][1] = {1e9, -1e9};
		if(a[i] >= a[i - 1])
			dp[i][0] = merge(dp[i][0], addone(dp[i - 1][0]));
		if(a[i] >= b[i - 1])
			dp[i][0] = merge(dp[i][0], addone(dp[i - 1][1]));
		if(b[i] >= a[i - 1])
			dp[i][1] = merge(dp[i][1], dp[i - 1][0]);
		if(b[i] >= b[i - 1])
			dp[i][1] = merge(dp[i][1], dp[i - 1][1]);
	}
	
	string res;
	int ac = 1;
	if(!(dp[n][0].X <= n / 2 && n / 2 <= dp[n][0].Y)) ac = 2;
	if(!(dp[n][0].X <= n / 2 && n / 2 <= dp[n][0].Y) && !(dp[n][1].X <= n / 2 && n / 2 <= dp[n][1].Y)) {
		printf("-1\n");
		return 0;
	}
	
	//~ cout << dp[n - 1][0].X << " "<< dp[n - 1][0].Y << endl;
	
	res += (ac == 1 ? 'A' : 'B');
	int c = n / 2;
	for(int i = n ; i >= 2 ; i--) {
		//~ cout << n << " " << c << endl;
		
		int aac = 1;
		if(ac == 1)
			c--;
		if(!(dp[i - 1][0].X <= c && c <= dp[i - 1][0].Y && ((ac == 1 && a[i] >= a[i - 1]) || (ac == 2 && b[i] >= a[i - 1]))))
			aac = 2;

		ac = aac;
		res += (ac == 1 ? 'A' : 'B');
	}
		
	reverse(res.begin(), res.end());
	printf("%s\n", res.c_str());
		
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building4.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
building4.cpp:28:8: 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