Submission #938823

#	Time	Username	Problem	Language	Result	Execution time	Memory
938823		pcc	Building 4 (JOI20_building4)	C++14	100 / 100	224 ms	40392 KiB

building4

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e6+10;
int N;
int arr[mxn][2];
int ch[mxn];
int need,cnt;

void chain(int s,int e){
	if(!cnt)return;
	//cout<<"CHAIN:"<<s<<' '<<e<<endl;
	pii big = make_pair(0,e+1);
	int sum = 0;
	for(int i = e;i>=s;i--){
		if(i != 1&&arr[i-1][ch[i-1]]>arr[i][ch[i]^1])break;
		if(i != N*2&&max(arr[i+1][0],arr[i+1][1])<arr[i][ch[i]^1])break;
		sum += (ch[i] == need?-1:1);
		if(sum == cnt)big = make_pair(mxn,i);
		else big = max(big,make_pair(sum,i));
	}
	for(int i = e;i>=big.sc;i--){
		ch[i] ^= 1;
	}
	cnt = max(0,cnt-big.fs);
	return;
}

void calc(int s,int e){
	if(s>e)return;
	//cout<<"calc:"<<s<<' '<<e<<endl;
	if(!cnt)return;
	vector<pii> v = {{s,s}};
	for(int i = s+1;i<=e;i++){
		//cout<<i<<":"<<arr[i-1][ch[i]^1]<<','<<arr[i][ch[i]]<<endl;
		if(arr[i-1][ch[i-1]^1]<=arr[i][ch[i]])v.push_back({i,i});
		else v.back().sc = i;
	}
	for(auto &i:v)chain(i.fs,i.sc);
}

void check(){
	bool flag = false;
	vector<int> cut = {0};
	for(int i = 1;i<=N*2;i++){
		if(arr[i][ch[i]]>arr[i][ch[i]^1])cut.push_back(i);
	}
	cut.push_back(N*2+1);
	for(int i = 1;i<cut.size();i++){
		calc(cut[i-1]+1,cut[i]-1);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 0;i<2;i++){
		for(int j = 1;j<=N*2;j++)cin>>arr[j][i];
	}
	if(arr[1][0]>arr[1][1])ch[1] = 1;
	for(int i = 2;i<=N*2;i++){
		if(arr[i][1]<arr[i][0])ch[i] = 1;
		if(arr[i][ch[i]]<arr[i-1][ch[i-1]])ch[i]^=1;
		if(arr[i][ch[i]]<arr[i-1][ch[i-1]]){
			cout<<"-1\n";
			return 0;
		}
	}
	int sum = 0;
	for(int i = 1;i<=N*2;i++)sum += ch[i];
	if(sum<N)need = 1,cnt = N-sum;
	else need = 0,cnt = sum-N;
	//for(int i = 1;i<=N*2;i++)cout<<ch[i];cout<<endl;
	//cout<<need<<','<<cnt<<endl;
	check();
	if(cnt){
		cout<<"-1";
		return 0;
	}
	for(int i = 1;i<=N*2;i++){
		cout<<"AB"[ch[i]];
	}
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'void check()':
building4.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i = 1;i<cut.size();i++){
      |                ~^~~~~~~~~~~
building4.cpp:51:7: warning: unused variable 'flag' [-Wunused-variable]
   51 |  bool flag = false;
      |       ^~~~

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