제출 #1285546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285546		Jawad_Akbar_JJ	건물 4 (JOI20_building4)	C++20	0 / 100	2113 ms	493028 KiB

building4

#include <iostream>

using namespace std;
const int N = 1<<20;
int a[N][2], Poss[N][2];
pair<int,int> Rng[N][2];

int main(){
	int n;
	cin>>n;
	n += n;

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

	Poss[0][0] = 1;
	Rng[0][0] = {0, 0};

	for (int i=1;i<=n;i++){
		for (int k : {0, 1}){
			for (int j : {0, 1}){
				if (Poss[i-1][j] == 0 or a[i-1][j] > a[i][k])
					continue;
				auto [l, r] = Rng[i][k];
				auto [L, R] = Rng[i-1][j];

				if (Poss[i][k] == 0)
					Rng[i][k] = {L + !k, R + !k};
				else
					Rng[i][k] = {min(L, l) + !k, max(R, r) + !k};
				Poss[i][k] = 1;
			}
		}
	}

	int I = n, J = 0, countA = n / 2;
	if (!Poss[I][J] or Rng[I][J].first > countA or Rng[I][J].second < countA)
		J = 1;
	if (!Poss[I][J] or Rng[I][J].first > countA or Rng[I][J].second < countA)
		return cout<<"-1\n", 0;

	string s;
	while (I != 0){
		s += char('A' + J);
		countA -= !J;
		for (int k : {0, 1}){
			if (Poss[I-1][k] and a[I-1][k] < a[I][J] and Rng[I-1][k].first <= countA and Rng[I-1][k].second >= countA){
				J = k, I--;
				break;
			}
		}
	}

	for (int i=n-1;i>=0;i--)
		cout<<s[i];
	cout<<'\n';
}

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