Submission #335216

#	Time	Username	Problem	Language	Result	Execution time	Memory
335216		CaroLinda	Building 4 (JOI20_building4)	C++14	100 / 100	403 ms	48236 KiB

building4

#include <bits/stdc++.h>

const int MAXN = 1e6+10 ;
const int inf = 1e9+7 ;

using namespace std;

int N ;
int dpMin[MAXN][2], dpMax[MAXN][2] ;

int main()
{	

	scanf("%d", &N ) ;
	N <<= 1 ;

	vector<int> A(N) , B(N) ;

	for(int i = 0 ; i < N ; i++ ) scanf("%d", &A[i] ) ;
	for(int i = 0 ; i < N ; i++ ) scanf("%d", &B[i] ) ;

	dpMin[0][0] = dpMax[0][0] = 1 ;
	dpMin[0][1] = dpMax[0][1] = 0 ;

	for(int i = 1 ; i < N ; i++ )
	{
		dpMin[i][0] = dpMin[i][1] = MAXN ;
		dpMax[i][0] = dpMax[i][1] = -1 ;

		//Testing if I'll put an A
		if( A[i] >= A[i-1] ) 
		{
			dpMin[i][0] = dpMin[i-1][0] + 1 ;
			dpMax[i][0] = dpMax[i-1][0] + 1 ;
		}
		if( A[i] >= B[i-1] ) 
		{
			dpMin[i][0] = min( dpMin[i][0] , 1 + dpMin[i-1][1] ) ;
			dpMax[i][0] = max( dpMax[i][0] , 1 + dpMax[i-1][1] ) ;
		}

		//Testing if I'll put a B
		if( B[i] >= A[i-1] ) 
		{
			dpMin[i][1] = dpMin[i-1][0] ;
			dpMax[i][1] = dpMax[i-1][0] ;
		}
		if( B[i] >= B[i-1] ) 
		{
			dpMin[i][1] = min(dpMin[i][1] , dpMin[i-1][1] ) ;
			dpMax[i][1] = max(dpMax[i][1] , dpMax[i-1][1] ) ;
		}
	}

	vector<int> ans(N) ;

	int aLeft = N>>1 ;

	for(int i = N-1 , toPut = -1 , afterMe = inf ; i >= 0 ; i--, toPut = -1 )
	{
		if( A[i] <= afterMe && dpMin[i][0] <= aLeft && aLeft <= dpMax[i][0] ) toPut = 0 ;
		if( B[i] <= afterMe && dpMin[i][1] <= aLeft && aLeft <= dpMax[i][1] ) toPut = 1 ;

		if(toPut == -1 )
		{
			printf("-1\n") ;
			return 0 ;
		}

		aLeft -= ( toPut == 0 ) ;
		afterMe = ( toPut == 0 ) ? A[i] : B[i] ;
		ans[i] = toPut ;

	}

	for(int i = 0 ; i < N ; i++ ) printf("%c", ( ans[i] == 0 ) ? 'A' : 'B' ) ;
	printf("\n") ;

}                                   	

Compilation message (stderr)

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

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