Submission #1181504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181504		catch_me_if_you_can	Building 4 (JOI20_building4)	C++20	0 / 100	1 ms	584 KiB

building4

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int INF = 1e17;


in merge(in x1, in x2)
{
	if(x1 == (in){-INF, -INF})
		return x2;
	else if(x2 == (in){-INF, -INF})
		return x1;
	else
		return {min(x1[0], x2[0]), max(x1[0], x2[0])};
}

in sp(in x, int u)
{
	if(u == 0)
		return x;
	if(x == (in){-INF, -INF})
		return x;
	else
		return {x[0]+1, x[1]+1};
}

bool belongs(int p, in x)
{
	return ((x[0] <= p) && (p <= x[1]));
}

signed main()
{
	fast();
	int n; cin >> n; n = 2*n;
	vector<in> x(n+1);
	for(int i = 1; i <= n; i++)
		cin >> x[i][0];
	for(int i = 1; i <= n; i++)
		cin >> x[i][1];
	in dp[n+1][2];
	dp[0][0] = {0,0};
	dp[0][1] = {0,0};
	x[0] = {0,0}; 
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			dp[i][j] = {-INF, -INF};
			for(int k = 0; k < 2; k++)
			{
				if(x[i-1][k] <= x[i][j])
					dp[i][j] = merge(dp[i][j], sp(dp[i-1][k], j));
			}
		}
	}
	if(belongs(n/2, dp[n][0]) || belongs(n/2, dp[n][1]))
	{
		int g = n/2;
		vector<char> c(n+1);
		int j = 0;
		if(belongs(g, dp[n][1]))
			j = 1; 
		for(int i = n; i >= 1; i--)
		{
			c[i] = 'A'+j;
			g-=j;
			for(int k = 0; k < 2; k++)
			{
				if(x[i-1][k] <= x[i][j])
				{
					if(belongs(g, dp[i-1][k]))
					{
						j = k;
						break;
					}
				}
			}
		}
		for(int i = 1; i <= n; i++)
			cout << c[i];
		cout << "\n";
	}
	else
		cout << "-1\n";
	return 0;
}	

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