제출 #1285667

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

building4

#include <iostream>

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

int main(){
	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, cnt = 0, Ind = -1;
	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;

	while (I != 0){
		Ans[I] = 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=1;i<n;i++){
		if (a[i][Ans[i] - 'A'] > a[i+1][Ans[i+1] - 'A']){
			Ind = i+1;
			// cout<<1 / 0;
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	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;

	while (I != 0){
		// Ans[I] = 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){
				if (I == Ind and a[I - 1][k] > a[I][J])
					cout<<1 / 0;
				J = k, I--;
				break;
			}
		}
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	for (int i=1;i<=n;i++)
		cout<<Ans[i];
	cout<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp: In function 'int main()':
building4.cpp:76:49: warning: division by zero [-Wdiv-by-zero]
   76 |                                         cout<<1 / 0;
      |                                               ~~^~~

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