Submission #6259733

---

Source Code Expand

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

int read(){
	int a = 0; char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		a = a * 10 + c - 48; c = getchar();
	}
	return a;
}

const int _ = 2e5 + 7;
int val[_] , cnt[_] , N;

bool cmp(int a , int b){return a > b;}

struct segTree{
	int mx[_ << 2];

	void init(){memset(mx , -0x3f , sizeof(mx));}

#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)

	void modify(int x , int l , int r , int tar , int val){
		if(l == r){mx[x] = val; return;}
		mid >= tar ? modify(lch , l , mid , tar , val) : modify(rch , mid + 1 , r , tar , val);
		mx[x] = max(mx[lch] , mx[rch]);
	}

	int qry(int x,  int l , int r , int L , int R){
		if(l >= L && r <= R) return mx[x];
		int Mx = -1e9;
		if(mid >= L) Mx = qry(lch , l , mid , L , R);
		if(mid < R) Mx = max(Mx , qry(rch , mid + 1 , r , L , R));
		return Mx;
	}
}T1 , T2;

bool check(int pos , int Mx1 , int Mx2 , int cnt1 , int cnt2){
	int V1 = cnt1 + cnt[pos] - cnt2 , V2 = cnt2 + cnt[pos] - cnt1;
	if(V1 >= 0)
		if(V1 & 1){if(T1.qry(1 , 1 , N , Mx2 , N) >= V1) return 1;}
		else if(T2.qry(1 , 1 , N , Mx2 , N) >= V1) return 1;
	if(V2 >= 0)
		if(V2 & 1){if(T1.qry(1 , 1 , N , Mx1 , N) >= V2) return 1;}
		else if(T2.qry(1 , 1 , N , Mx1 , N) >= V2) return 1;
	return 0;
}

int main(){
	N = read();
	int pre = 0;
	for(int i = 1 ; i <= N ; ++i){
		val[i] = read(); cnt[i] = val[i] > pre;
		pre = max(pre , val[i]);
	}
	for(int i = N ; i ; --i) cnt[i] += cnt[i + 1];
	T1.init();
	for(int i = N ; i ; --i){
		int p0 = T1.qry(1 , 1 , N , val[i] , N) , p1 = T2.qry(1 , 1 , N , val[i] , N);
		if(cnt[i] > cnt[i + 1]){
			T1.modify(1 , 1 , N , val[i] , p0 + 2);
			T2.modify(1 , 1 , N , val[i] , p1 + 2);
		}
		else{
			T1.modify(1 , 1 , N , val[i] , p1 + 1);
			T2.modify(1 , 1 , N , val[i] , p0 + 1);
		}
	}
	vector < int > arr1 , arr2; string s;
	int Mx1 = 1 , Mx2 = 1 , cnt1 = 0 , cnt2 = 0;
	for(int i = 1 ; i <= N ; ++i){
		T1.modify(1 , 1 , N , val[i] , -1e9);
		T2.modify(1 , 1 , N , val[i] , 0);
		if(check(i + 1 , max(Mx1 , val[i]) , Mx2 , cnt1 + (Mx1 <= val[i]) , cnt2)){
			arr1.push_back(val[i]); cnt1 += Mx1 <= val[i]; Mx1 = max(Mx1 , val[i]);
			s.push_back('0');
		}
		else{
			arr2.push_back(val[i]); cnt2 += Mx2 <= val[i]; Mx2 = max(Mx2 , val[i]);
			s.push_back('1');
		}
	}
	if(cnt1 == cnt2) cout << s;
	else cout << -1;
	return 0;
}

Submission Info

Judge Result