Submission #249756

#	Time	Username	Problem	Language	Result	Execution time	Memory
249756		etienne	Building 4 (JOI20_building4)	C++14	100 / 100	409 ms	45536 KiB

building4

#include<cstdio>
#include <algorithm>
using namespace std;

const int oo=1e9;
int N;
int A[2*1000*1000][2];
int mini[2*1000*1000][2],maxi[2*1000*1000][2];
char res[2*1000*1000];

int main(){
	scanf("%d",&N);
	N*=2;
	for(int i=0;i<N;i++)scanf("%d", &A[i][0]);
	for(int i=0;i<N;i++)scanf("%d", &A[i][1]);
	for(int i=1;i<N;i++)mini[i][0]=mini[i][1]=+oo;
	for(int i=1;i<N;i++)maxi[i][0]=maxi[i][1]=-oo;
	mini[0][0]=maxi[0][0]=1;
	mini[0][1]=maxi[0][1]=-1;
	
	for(int i=1;i<N;i++){
		if(A[i][0]>=A[i-1][0]){
			mini[i][0]=min(mini[i][0], mini[i-1][0]+1);
			maxi[i][0]=max(maxi[i][0], maxi[i-1][0]+1);
		}
		if(A[i][0]>=A[i-1][1]){
			mini[i][0]=min(mini[i][0], mini[i-1][1]+1);
			maxi[i][0]=max(maxi[i][0], maxi[i-1][1]+1);
		}
		if(A[i][1]>=A[i-1][0]){
			mini[i][1]=min(mini[i][1], mini[i-1][0]-1);
			maxi[i][1]=max(maxi[i][1], maxi[i-1][0]-1);
		}
		if(A[i][1]>=A[i-1][1]){
			mini[i][1]=min(mini[i][1], mini[i-1][1]-1);
			maxi[i][1]=max(maxi[i][1], maxi[i-1][1]-1);
		}
	}
	int pos, nb;
	if(mini[N-1][0]<=0 && 0<=maxi[N-1][0]){
		pos=0;
		nb=-1;
		res[N-1]='A';
	}
	else if(mini[N-1][1]<=0 && 0<=maxi[N-1][1]){
		pos=1;
		nb=+1;
		res[N-1]='B';
	}
	else{
		printf("-1\n");
		return 0;
	}
	for(int i=N-2;i>=0;i--){
		if(A[i][0]<=A[i+1][pos]&&mini[i][0]<=nb&&nb<=maxi[i][0]){
			res[i]='A';
			pos=0;
			nb--;
		}
		else{
			res[i]='B';
			pos=1;
			nb++;
		}
	}
	printf("%s\n",res );
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
building4.cpp:14:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<N;i++)scanf("%d", &A[i][0]);
                      ~~~~~^~~~~~~~~~~~~~~~
building4.cpp:15:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<N;i++)scanf("%d", &A[i][1]);
                      ~~~~~^~~~~~~~~~~~~~~~

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