제출 #1213088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213088		salmon	Building 4 (JOI20_building4)	C++20	100 / 100	191 ms	26036 KiB

building4

#include <bits/stdc++.h>
using namespace std;

int N;
int A[1100100];
int B[1100100];
pair<int,int> big[1100100];
pair<int,int> small[1100100];

pair<int,int> onion(pair<int,int> ii, pair<int,int> ii1){
	if(ii.first == -1) return ii1;
	if(ii1.first == -1) return ii;
	return {min(ii.first,ii1.first),max(ii.second,ii1.second)};
}

int main(){	

	scanf(" %d",&N);
	
	for(int i = 0; i < N * 2; i++){
		scanf(" %d",&A[i]);
	}
	
	for(int i = 0; i < N * 2; i++){
		scanf(" %d",&B[i]);
	}
	
	bool die = false;
	
	big[0] = {0,0};
	small[0] = {1,1};
	
	if(A[0] > B[0]) swap(big[0],small[0]);
	
	for(int i = 1; i < N * 2; i++){		
		if(max(A[i],B[i]) < min(A[i - 1], B[i - 1]) ){
			die = true;
			break;
		}
		

		if(max(A[i - 1], B[i - 1])  <= B[i]){
			if(small[i - 1].first == -1){
				big[i] = big[i - 1];
			}
			else{
				big[i] = {min(big[i - 1].first, small[i - 1].first), max(big[i - 1].second, small[i - 1].second )};
			}
		}
		else if(min(A[i - 1], B[i - 1]) <= B[i]){
			big[i] = small[i - 1];
		}
		else big[i] = {-1,-1};
		
		
		if(max(A[i - 1], B[i - 1])  <= A[i]){
			if(small[i - 1].first == -1){
				small[i] = big[i - 1];
			}
			else{
				small[i] = {min(big[i - 1].first, small[i - 1].first), max(big[i - 1].second, small[i - 1].second )};
			}
			small[i].first++;
			small[i].second++;
		}
		else if(min(A[i - 1], B[i - 1]) <= A[i] && small[i - 1].first != -1){
			small[i] = small[i - 1];
			small[i].first++;
			small[i].second++;
		}
		else small[i] = {-1,-1};
			
		if(B[i] < A[i]) swap(big[i],small[i]);
	}
	
	if(die){
		printf("-1\n");
	}
	else{
		pair<int,int> ii = onion(big[N * 2 - 1], small[N * 2 - 1]);
		
		if(N < ii.first || ii.second < N ){
			printf("-1\n");
		}
		else{
		
			int num = N;
			vector<char> ans;
			
			for(int i = N * 2 - 1; i >= 0; i--){
				if(small[i].first <= num && num <= small[i].second){
					if(A[i] <= B[i]){
						ans.push_back('A');
						num--;
					}
					else ans.push_back('B');
				}
				else{
					if(A[i] > B[i]){
						ans.push_back('A');
						num--;
					}
					else ans.push_back('B');
				}
			}
			
			reverse(ans.begin(),ans.end());
			
			for(char c : ans) printf("%c",c);
		}
	}
}

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

building4.cpp: In function 'int main()':
building4.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
building4.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |                 scanf(" %d",&A[i]);
      |                 ~~~~~^~~~~~~~~~~~~
building4.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~

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