Submission #837810

#	Time	Username	Problem	Language	Result	Execution time	Memory
837810		MohamedAhmed04	Building 4 (JOI20_building4)	C++14	100 / 100	228 ms	42448 KiB

building4

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

int a[MAX] , b[MAX] ;
int n ;

int take_min[MAX] , take_max[MAX] , take_free[MAX] ;

int taken[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < 2*n ; ++i)
		cin>>a[i] ;
	for(int i = 0 ; i < 2*n ; ++i)
		cin>>b[i] ;
	for(int i = 0 ; i < 2*n-1 ; ++i)
	{
		if(min(a[i] , b[i]) > max(a[i+1] , b[i+1]))
			return cout<<-1<<"\n" , 0 ;
		if(min(a[i] , b[i]) > min(a[i+1] , b[i+1]))
			take_max[i+1] = 1 ;
		else if(take_max[i] && max(a[i] , b[i]) > min(a[i+1] , b[i+1]))
			take_max[i+1] = 1 ;
	}
	for(int i = 2*n-1 ; i > 0 ; --i)
	{
		if(max(a[i] , b[i]) < max(a[i-1] , b[i-1]))
			take_min[i-1] = 1 ;
		else if(take_min[i] && min(a[i] , b[i]) < max(a[i-1] , b[i-1]))
			take_min[i-1] = 1 ;
	}
	for(int i = 0 ; i < 2*n ; ++i)
	{
		if(take_max[i] && take_min[i])
			return cout<<-1<<"\n" , 0 ;
		if(take_max[i] || take_min[i])
			continue ;
		take_free[i] = 1 ;
		if(i-1 >= 0 && (min(a[i] , b[i]) < max(a[i-1] , b[i-1]) && !take_min[i-1]))
			take_free[i] = 0 ;
		if(i+1 < 2*n && (max(a[i] , b[i]) > min(a[i+1] , b[i+1]) && !take_max[i+1]))
			take_free[i] = 0 ;
	}
	vector< vector< pair<int , int> > >vp ;
	bool flag = false ;
	int ans = 0 , cnt = 0 ;
	for(int i = 0 ; i < 2*n ; ++i)
	{
		flag &= (!take_free[i] && !take_max[i] && !take_min[i]) ;
		if(take_max[i])
		{
			if(a[i] > b[i])
				ans++ , taken[i] = 0 ;
			else
				ans-- , taken[i] = 1 ;
		}
		else if(take_min[i])
		{
			if(a[i] < b[i])
				ans++ , taken[i] = 0 ;
			else
				ans-- , taken[i] = 1 ;
		}
		else if(take_free[i])
			cnt++ ;
		else
		{
			if(!flag)
				vp.push_back({}) ;
			else
			{
				if(min(a[i] , b[i]) >= max(a[i-1] , b[i-1]))
					vp.push_back({}) ;
			}
			if(a[i] > b[i])
				ans++ , taken[i] = 0 , vp.back().emplace_back(-2 , i) ;
			else
				ans-- , taken[i] = 1 , vp.back().emplace_back(2 , i) ;
			flag = true ;
		}
	}
	for(auto &v2 : vp)
	{
		int Max = 0 , Min = 0 , sum = 0 ;
		for(auto &p : v2)
		{
			sum += p.first ;
			Max = max(Max , sum) , Min = min(Min , sum) ;
		}
		if(ans > 0)
		{
			int a = min(-1 * Min , ans) ;
			if((a & 1))
				a -= (a & 1) ;
			ans -= a ;
			sum = 0 ;
			for(auto &p : v2)
			{
				if(-1 * sum == a)
					break ;
				taken[p.second] ^= 1 ;
				sum += p.first ;
			}
		}
		else
		{
			int a = min(Max , -1 * ans) ;
			if((a & 1))
				a -= (a & 1) ;
			ans += a ;
			sum = 0 ;
			for(auto &p : v2)
			{
				if(sum == a)
					break ;
				taken[p.second] ^= 1 ;
				sum += p.first ;
			}
		}
	}
	for(int i = 0 ; i < 2*n ; ++i)
	{
		if(take_free[i])
		{
			if(ans < 0)
				taken[i] = 0 , ans++ ;
			else
				taken[i] = 1 , ans-- ;
		}
	}
	if(ans != 0)
		return cout<<-1<<"\n" , 0 ;
	for(int i = 0 ; i < 2*n ; ++i)
		cout<<(char)('A' + taken[i]) ;
	cout<<"\n" ;
	return 0 ;
}		

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