Submission #442493

#	Time	Username	Problem	Language	Result	Execution time	Memory
442493		kig9981	Building 4 (JOI20_building4)	C++17	100 / 100	321 ms	45396 KiB

building4

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int A[1000001][2], L[1000001][2], R[1000001][2];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, v, b=0;
	string ans;
	cin>>N; memset(L,0x7f,sizeof(L)); memset(R,0x80,sizeof(R));
	L[0][0]=L[0][1]=R[0][0]=R[0][1]=0;
	for(int i=1;i<=2*N;i++) cin>>A[i][0];
	for(int i=1;i<=2*N;i++) {
		cin>>A[i][1];
		for(int j=0;j<2;j++) if(L[i-1][j]<=R[i-1][j]) for(int k=0;k<2;k++) if(A[i-1][j]<=A[i][k]) {
			L[i][k]=min(L[i][k],L[i-1][j]+(k ? 1:-1));
			R[i][k]=max(R[i][k],R[i-1][j]+(k ? 1:-1));
		}
	}
	if(L[2*N][0]<=0 && 0<=R[2*N][0]) v=0;
	else if(L[2*N][1]<=0 && 0<=R[2*N][1]) v=1;
	else {
		cout<<"-1\n";
		return 0;
	}
	for(int i=2*N;--i;) {
		ans.push_back('A'+v);
		b-=v ? 1:-1;
		for(int j=0;j<2;j++) if(A[i][j]<=A[i+1][v] && L[i][j]<=b && b<=R[i][j]) {
			v=j;
			break;
		}
	}
	ans.push_back('A'+v);
	reverse(ans.begin(),ans.end());
	cout<<ans<<'\n';
	return 0;
}

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