Submission #386982

#	Time	Username	Problem	Language	Result	Execution time	Memory
386982		MohamedAhmed04	건물 4 (JOI20_building4)	C++14	0 / 100	2 ms	492 KiB

building4

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

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

vector< vector<int> >v ;

int diff = 0 ;

int f(char c)
{
	if(c == 'A')
		return 1 ;
	else
		return -1 ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	n *= 2 ; 
	for(int i = 0 ; i < n ; ++i)
		cin>>a[i] ;
	for(int i = 0 ; i < n ; ++i)
		cin>>b[i] ;
	ans[0] = 'A' ;
	for(int i = 1 ; i < n ; ++i)
	{
		ans[i] = 'A' ;
		int x = min(a[i-1] , b[i-1]) ;
		if(x > max(a[i] , b[i]))
			return cout<<-1<<"\n" , 0 ;
		else if(a[i] >= x && b[i] < x)
			b[i] = -1 ;
		else if(a[i] < x && b[i] >= x)
			ans[i] = 'B' , a[i] = -1 ;
	}
	for(int i = n-2 ; i >= 0 ; --i)
	{
		int x = max(a[i+1] , b[i+1]) ;
		if(x < min(a[i] , b[i]))
			return cout<<-1<<"\n" , 0 ;
		else if(a[i] <= x && b[i] > x)
			b[i] = -1 ;
		else if(a[i] > x && b[i] <= x)
			ans[i] = 'B' , a[i] = -1 ;
	}
	int diff = 0 ;
	bool flag = false ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(max(a[i] , b[i]) < 0)
			return cout<<-1<<"\n" , 0 ;
		if(min(a[i] , b[i]) < 0)
		{
			flag = false ;
			diff += f(ans[i]) ;
			continue ;
		}
		if(a[i] >= b[i])
			ans[i] = 'A' ;
		else
			ans[i] = 'B' ;
		diff += f(ans[i]) ;
		if(flag && max(a[i-1] , b[i-1]) > min(a[i] , b[i]))
			v.back().push_back(i) ;
		else
			v.push_back({i}) ;
		flag = true ;
	}
	if(abs(diff) % 2 != 0)
		return cout<<-1<<"\n" , 0 ;
	diff /= 2 ;
	for(auto &v1 : v)
	{
		int now = diff ;
		int idx = -1 ;
		for(int i = 0 ; i < v1.size() ; ++i)
		{
			char c = ans[v1[i]] ;
			if(c == 'A')
				now-- ;
			else
				now++ ;
			if(abs(now) < abs(diff))
				idx = i , diff = now ;
		}
		for(int i = 0 ; i <= idx ; ++i)
		{
			if(ans[v1[i]] == 'A')
				ans[v1[i]] = 'B' ;
			else
				ans[v1[i]] = 'A' ;
		}
	}
	if(diff != 0)
		return cout<<-1<<"\n" , 0 ;
	for(int i = 0 ; i < n ; ++i)
		cout<<ans[i] ;
	cout<<"\n" ;
	return 0 ;
}		

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i = 0 ; i < v1.size() ; ++i)
      |                   ~~^~~~~~~~~~~

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