Submission #772489

#	Time	Username	Problem	Language	Result	Execution time	Memory
772489		Mohammad_Parsa	Building 4 (JOI20_building4)	C++17	100 / 100	706 ms	321860 KiB

building4

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=2e6+7;
int l[N],n,c,a,b,x[N],y[N],mn[N],mx[N],k,t[N],m[N],inf=1e9+7,d1[N],d2[N],mark[N];
char ans[N];
vector<int>v1[N],v2[N];
queue<pair<int,pair<int,int>>>st;

int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<2*n;i++)cin>>x[i];
	x[2*n]=1e9;
	for(int i=0;i<2*n;i++)cin>>y[i];
	y[2*n]=1e9;
	int u=2*n;
	for(int i=0;i<2*n;i++){
		int p=x[i+1],q=y[i+1];
		if(x[i]<=p){
			v1[i].pb(i+1);d1[i]++;
			v2[i+1].pb(i);d2[i+1]++;
		}
		if(x[i]<=q){
			v1[i].pb(i+1+u);d1[i]++;
			v2[i+1+u].pb(i);d2[i+1+u]++;
		}
		if(y[i]<=p){
			v1[i+u].pb(i+1);d1[i+u]++;
			v2[i+1].pb(i+u);d2[i+1]++;
		}
		if(y[i]<=q){
			v1[i+u].pb(i+1+u);d1[i+u]++;
			v2[i+1+u].pb(i+u);d2[i+1+u]++;
		}
	}
	for(int i=0;i<4*n;i++){
		if(i%u!=2*n-1) st.push(mk(d1[i],mk(i,1)));
		if(i%u!=0)st.push(mk(d2[i],mk(i,2)));
	}
	//cout<<d1[1]<<" "<<d2[1]<<endl;
	while(st.size()){
		
		int i=st.front().S.F,val=st.front().F,ff=st.front().S.S;
		st.pop();
		
		if(mark[i]) continue;
		if(ff==1){
			if(d1[i]!=val || val>0) continue;
		}
		else{
			if(d2[i]!=val || val>0) continue;
		}
		//cout<<i<<endl;
		mark[i]=1;
		if(mark[i%u] && mark[i%u+u]){
			cout<<-1;
			return 0;
		}
		//cout<<i<<endl;
		for(auto y:v1[i]){
			if(!mark[y]){
				//st.erase(mk(d2[y],mk(y,2)));
				d2[y]--;
				st.push(mk(d2[y],mk(y,2)));
			}
		}
		for(auto y:v2[i]){
			if(!mark[y]){
				//st.erase(mk(d1[y],mk(y,1)));
				d1[y]--;
				st.push(mk(d1[y],mk(y,1)));
			}
		}
	}
	for(int i=0;i<2*n;i++){
		if(mark[i])x[i]=inf;
		if(mark[i+u])y[i]=inf;

		if(x[i]==inf && y[i]==inf){
			cout<<-1;
			return 0;
		}
		else if(x[i]!=inf && y[i]!=inf){
			if(max(x[i],y[i])<=min(x[i+1],y[i+1])){
				c++;
			}
			else{
				m[i]=1;
				//cout<<i<<endl;
			}
		}
		else if(x[i]!=inf || y[i]!=inf){
			if(x[i]==inf){
				b++;
				//cout<<i<<endl;
			}
			else{
				a++;
			}
		}
	}

	//cout<<a<<" "<<b<< " "<<c<<endl;
	string s;
	int M=0;
	for(int i=0;i<2*n;){
		if(!m[i]){
			i++;
			continue;
		}
		s="";
		int f=0;
		while(m[i]){
			if(x[i]>y[i]){
				s+='A';
				f++;
			}
			else{
				s+='B';
			}
			i++;
		}
		if(x[i]!=inf && y[i]!=inf){
			if(i<2*n) c--;
		if(x[i]>y[i]){
			s+='A';
			f++;
		}
		else{
			s+='B';
		}
		i++;
		}
		mn[k]=f;mx[k]=f;
		for(auto w:s){
			if(w=='A'){
				f--;
			}
			else{
				f++;
			}
			mn[k]=min(mn[k],f);
			mx[k]=max(mx[k],f);
		}
		M+=mn[k];
		t[k]=mn[k];
		k++;
	}
	if(M>n-a){
		cout<<-1;
		return 0;
	}
	int r=n-a-c;
	for(int i=0;i<k;i++){
		while(M<r && t[i]<mx[i]){
			M++;
			t[i]++;
		}
	}
	if(M<r){
		cout<<-1;
		return 0;
	}
	fill(ans,ans+N,'f');
	int g=0;
	for(int i=0;i<2*n;){
		if(!m[i]){
			i++;
			continue;
		}
		int h=i;
		s="";
		int f=0;
		while(m[i]){
			if(x[i]>y[i]){
				s+='A';
				f++;
			}
			else{
				s+='B';
			}
			i++;
		}
		if(x[i]!=inf && y[i]!=inf){
		if(x[i]>y[i]){
			s+='A';
			f++;
		}
		else{
			s+='B';
		}
		i++;
		}
		string z;
		if(f==t[g]){
			z=s;
		}
		for(int j=0;j<s.size();j++){
			char w=s[j];
			if(w=='A'){
				f--;
				s[j]='B';
			}
			else{
				f++;
				s[j]='A';
			}
			if(f==t[g]){
				z=s;
				break;
			}
		}
		a+=t[g];
		for(int j=h;j<i;j++){
			ans[j]=z[j-h];
		}
		g++;
	}	
	for(int i=0;i<2*n;i++){
		//cout<<ans[i];
	}
	//cout<<endl;
	for(int i=0;i<2*n;i++){
		if(ans[i]!='f') continue;
		if(x[i]!=inf && y[i]!=inf){
			if(a<n){
				ans[i]='A';
				a++;
			}
			else{
				ans[i]='B';
			}
			
		}
		else if(x[i]!=inf || y[i]!=inf){
			if(x[i]==inf){
				ans[i]='B';
			}
			else{
				ans[i]='A';
			}
		}
	}
	int e=0;
	for(int i=0;i<2*n;i++){
		if(ans[i]=='A')l[i]=x[i];
		else l[i]=y[i];
		if(i!=0 && l[i]<l[i-1]){
			e=1;
		}
	}
	if(e){
		cout<<-1;
		return 0;
	}
	for(int i=0;i<2*n;i++){
		cout<<ans[i];
	}

}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:207:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |   for(int j=0;j<s.size();j++){
      |               ~^~~~~~~~~

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