Submission #423656

#	Time	Username	Problem	Language	Result	Execution time	Memory
423656		p_square	Building 4 (JOI20_building4)	C++14	100 / 100	1282 ms	68892 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define mp make_pair
#define se second
#define fi first

int main()
{
	int m;
	cin>>m;
	int n = 2*m;
	int a[n], b[n];
	pair <int, int> mxaa[n], mxab[n], mxbb[n], mxba[n];

	for(int i = 0; i<n; i++)
	{
		cin>>a[i];
	}
	for(int i = 0; i<n; i++)
	{
		cin>>b[i];
	}

	for(int i = 0; i<n; i++)
	{
		mxaa[i] = mp(-1,-1);
		mxab[i] = mp(-1,-1);
		mxba[i] = mp(-1,-1);
		mxbb[i] = mp(-1,-1);
	}
	mxaa[0].fi = 1;
	mxbb[0].fi = 1;
	mxab[0].fi = 0;
	mxba[0].fi = 0;
	for(int i = 1; i<n; i++)
	{
		if(a[i] >= a[i-1])
		{
			mxaa[i] = max(mxaa[i], mp(mxaa[i-1].fi+1, 0));
			mxab[i] = max(mxab[i], mp(mxab[i-1].fi, 0));
		}
		if(a[i] >= b[i-1])
		{
			mxaa[i] = max(mxaa[i], mp(mxba[i-1].fi+1, 1));
			mxab[i] = max(mxab[i], mp(mxbb[i-1].fi, 1));
		}

		if(b[i] >= a[i-1])
		{
			mxba[i] = max(mxba[i], mp(mxaa[i-1].fi, 0));
			mxbb[i] = max(mxbb[i], mp(mxab[i-1].fi+1, 0));
		}

		if(b[i] >= b[i-1])
		{
			mxba[i] = max(mxba[i], mp(mxba[i-1].fi, 1));
			mxbb[i] = max(mxbb[i], mp(mxbb[i-1].fi+1, 1));
		}
	}

	int ans = -1;

	if(mxaa[n-1].fi >= m && mxab[n-1].fi >= m)
	{
		ans = 0;
	}
	if(mxba[n-1].fi >= m && mxbb[n-1].fi >= m)
	{
		ans = 1;
	}

	if(ans == -1)
	{
		cout<<ans;
		return 0;
	}

	int plana[n], planb[n];
	plana[n-1] = ans;
	planb[n-1] = ans;

	for(int i = n-1; i>0; i--)
	{
		if(plana[i] == 0)
		{
			plana[i-1] = mxaa[i].se; 
		}
		if(plana[i] == 1)
		{
			plana[i-1] = mxba[i].se;
		}
		if(planb[i] == 0)
		{
			planb[i-1] = mxab[i].se; 
		}
		if(planb[i] == 1)
		{
			planb[i-1] = mxbb[i].se;
		}
	}

	int alead = m, blead = m;
	if(ans == 0)
	{
		alead = mxaa[n-1].fi;
		blead = mxab[n-1].fi;
	}
	
	if(ans == 1)
	{
		alead = mxba[n-1].fi;
		blead = mxbb[n-1].fi;
	}

	/*
	for(int i = 0; i<n; i++)
	{
		cout<<plana[i]<<" "<<planb[i]<<endl;
	}
	cout<<alead<<blead<<endl;
	*/

	assert(alead >= m && blead >= m);

	int loc = n;
	while(alead != m && blead != m)
	{
		assert(loc >= 0);
		loc--;
		if(plana[loc] == planb[loc])
		{
			continue;
		}

		if(plana[loc] == 0 && a[loc] >= b[loc])
		{
			blead--;
			planb[loc] = 0;
		}
		else if(plana[loc] == 0 && b[loc] >= a[loc])
		{
			alead--;
			plana[loc] = 1;
		}
		else if(plana[loc] == 1 && a[loc] >= b[loc])
		{
			alead++;
			plana[loc] = 0;
		}
		else if(plana[loc] == 1 && b[loc] >= a[loc])
		{
			blead++;
			planb[loc] = 1;
		}
	}

	string S = "";

	if(alead == m && ans != -1)
	{
		for(int i = 0; i<n; i++)
		{
			if(plana[i] == 0)
				S+="A";
			else
				S+="B";
		}
	}
	else if(blead == m && ans != -1)
	{
		for(int i = 0; i<n; i++)
		{
			if(planb[i] == 0)
				S+="A";
			else
				S+="B";
		}
	}
	cout<<S;
	cout<<endl;

}

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