Submission #218908

#	Time	Username	Problem	Language	Result	Execution time	Memory
218908		dvdg6566	Building 4 (JOI20_building4)	C++14	100 / 100	392 ms	69652 KiB

building4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const int MAXN = 1000100;
const ll INF = 1e18;
int done[MAXN];
int A[MAXN];
int B[MAXN];
int flip[MAXN];
int N;
vi V;
vi rev;
int cfm[MAXN];
int wgt[MAXN];
int tot;
vi tmp;
int knapflip[MAXN];

void die(){
	cout<<-1;
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N;N*=2;
	for (int i=1;i<=N;++i)cin>>A[i];
	for (int i=1;i<=N;++i){
		cin>>B[i];
		if (A[i] > B[i]){swap(A[i], B[i]);flip[i] = 1;}
	}
	V.pb(0);
	for (int i=1;i<=N;++i){
		if (A[i] >= V.back())V.pb(A[i]);
		else {
			if (B[i] < V.back()){
				die();
			}else{
				V.pb(B[i]);
				if (flip[i] == 0)done[i] = 2;
				else done[i]=1;
			}
		}
	}
	rev.pb(INF);
	for (int i=N;i>=1;--i){
		if (B[i] <= rev.back())rev.pb(B[i]);
		else if (A[i] <= rev.back()){
			rev.pb(A[i]);
			if (done[i]){
				die();
			}
			if (flip[i] == 0)done[i] = 1;
			else done[i]=2;
		}else{
			die();
		}
	}
	int acnt=0;
	int bcnt=0;
	vi leftovers;
	for (int i=1;i<=N;++i){
		cfm[i] = 1;
		if (done[i] == 0){
			leftovers.pb(i);
			cfm[i] = 0;
			if(flip[i] == 0)done[i] = 1;
			else done[i] = 2;
		}else{
			if (done[i]==1)++acnt;
			else ++bcnt;
		}
		if (done[i] == 1)--tot;
		else ++tot;
	}
	//cout<<tot<<'\n';
	
	if (max(acnt, bcnt) > N/2){
		die();
	}
	vpi store;
	//for (auto i:leftovers)cout<<A[i]<<' '<<B[i]<<'\n';
	int curind = SZ(leftovers)-1;
	int cur = curind;
	while (cur){
		--cur;
		//cout<<leftovers[cur]<<' '<<leftovers[cur+1]<<'\n';
		if (B[leftovers[cur]] <= A[leftovers[cur+1]]){
			store.pb(cur+1, curind);
			curind = cur;
		}
	}
	store.pb(0,curind);
	for (auto i : store){
		if (tot==0)break;
		int a = i.f;
		int b = i.s;
		//cout<<"Range "<<a<<' '<<b<<'\n';
		//cout<<"Total "<<tot<<'\n';
		tmp.clear();
		tmp.pb(0);
		for (int i=b;i>=a;--i){
			assert(cfm[leftovers[i]] == 0);
			int t = -1;
			if (done[leftovers[i]] == 1)t = 2;
			else t = -2;
			tmp.pb(t + tmp.back());
		}
		reverse(ALL(tmp));
		//for (auto i : tmp)cout<<i<<' ';cout<<'\n';
		pi maxele=mp(-INF,INF);
		pi minele=mp(INF,INF);
		for (int i=0;i<SZ(tmp);++i){
			int x = tmp[i];
			if (x > maxele.f)maxele=mp(x,i+a);
			if(x < minele.f)minele=mp(x,i+a);
			if (x+tot == 0){
				for (int tt=i+a;tt<=b;++tt)knapflip[leftovers[tt]] = 1;
				tot = 0;
				break;
			}
		}
		//cout<<tot<<' '<<minele.f<<'\n';
		if (tot==0)break;
		if (tot < 0){
			for (int tt=maxele.s;tt<=b;++tt)knapflip[leftovers[tt]] = 1;
			tot += maxele.f;
		}else{
			for (int tt=minele.s;tt<=b;++tt)knapflip[leftovers[tt]] = 1;
			tot += minele.f;
		}
	}
	//cerr<<tot<<'\n';
	if (tot !=0){
		die();
	}
	for (int i=1;i<=N;++i)if (knapflip[i])done[i] = 3-done[i];
	
	
	for (int i=1;i<=N;++i){
		if (done[i] == 1){
			cout<<'A';	
		}else{
			cout<<'B';
		}
	}
}

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