Submission #211738

#	Time	Username	Problem	Language	Result	Execution time	Memory
211738		nibnalin	Building 4 (JOI20_building4)	C++17	100 / 100	450 ms	105848 KiB

building4

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(1e6)+5, inf = int(1e9)+5;

int n, A[maxn], B[maxn];
pair<int, int> memo[maxn][2];

pair<int, int> DP(int idx, int prev)
{
	if(idx > 2*n) return {0, 0};
	else if(memo[idx][prev].first != -1) return memo[idx][prev];
	else
	{
		int p = prev?B[idx-1]:A[idx-1];
		pair<int, int> res = {inf, -inf}, tmp;
		if(A[idx] >= p)
		{
			tmp = DP(idx+1, 0);
			res.first = min(res.first, tmp.first+1);
			res.second = max(res.second, tmp.second+1);
		}
		if(B[idx] >= p)
		{
			tmp = DP(idx+1, 1);
			res.first = min(res.first, tmp.first);
			res.second = max(res.second, tmp.second);
		}

		return memo[idx][prev] = res;
	}
}

int main(void)
{
	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++) memo[i][0] = memo[i][1] = {-1, -1};

	pair<int, int> res = DP(1, 0);
	if(!(res.first <= n && n <= res.second))
	{
		printf("-1\n");
		return 0;
	}

	int cur = 0, idx = 1, prev = 0;

	while(idx <= 2*n)
	{
		int p = prev?B[idx-1]:A[idx-1];
		pair<int, int> tmp;
		if(A[idx] >= p)
		{
			tmp = DP(idx+1, 0);
			if(tmp.first+1 <= n-cur && n-cur <= tmp.second+1)
			{
				printf("A");
				prev = 0;
				idx++, cur++;
				continue;
			}
		}
		if(B[idx] >= p)
		{
			tmp = DP(idx+1, 1);
			if(tmp.first <= n-cur && n-cur <= tmp.second)
			{
				printf("B");
				prev = 1;
				idx++;
				continue;
			}
		}
	}
	printf("\n");
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building4.cpp:39:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= 2*n;i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~
building4.cpp:40:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= 2*n;i++) scanf("%d", &B[i]);
                              ~~~~~^~~~~~~~~~~~~

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