Submission #5005405


Source Code Expand

Copy
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
	typedef long long ll;
	#define double long double
	const int INF=0x3f3f3f3f;
	const ll LLINF=0x3f3f3f3f3f3f3f3fll;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);puts("");}
	#define FR first
	#define SE second
	#define MP make_pair
	#define pr pair<int,int>
	#define PB push_back
	#define vc vector
	void chmax(int &x,const int y) {x=x>y?x:y;}
	void chmin(int &x,const int y) {x=x<y?x:y;}
	const int MAX_N=2e5+10;
	const ll MOD=1e9+7;
	void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
	
	struct BIT
	{
		vc<int> bit[MAX_N];int now[MAX_N];BIT(){memset(now,0,sizeof now);}
		#define lowbit(x) ((x)&-(x))
		void change(int x,int c){while(x<MAX_N) bit[x].PB(max(bit[x][now[x]],c)),now[x]++,x+=lowbit(x);}
		int ask(int x){int ans=-INF;while(x>=1) chmax(ans,bit[x][now[x]]),x-=lowbit(x);return ans;}
		void gaygay(int x){while(x<MAX_N) now[x]--,x+=lowbit(x);}
	}bit[2];
	int a[MAX_N];vc<int> ans;
	int c[2],mi[2],cnt[MAX_N];
	bool check(int i,int now)
	{
		int tmp1=c[now],tmp2=mi[now];
		if(a[i]<mi[now]) c[now]++,mi[now]=a[i];
		for(int j=0;j<=1;j++)
		{
			int wt=c[j]-c[j^1]+cnt[i+1];if(wt<0) continue;
			if(bit[wt&1].ask(mi[j^1])>=wt) return 1;
		}
		c[now]=tmp1;mi[now]=tmp2;
		return 0;
	}
	void main()
	{
		for(int i=1;i<MAX_N;i++) bit[0].bit[i].PB(0);
		for(int i=1;i<MAX_N;i++) bit[1].bit[i].PB(-1);
		
		int n=qread();for(int i=1;i<=n;i++) a[i]=n-qread()+1;
		int lstmi=INF;for(int i=1;i<=n;i++) if(a[i]<lstmi) lstmi=a[i],cnt[i]=1; else cnt[i]=0;
		for(int i=n;i>=1;i--) cnt[i]+=cnt[i+1];
		
		for(int i=n;i>=1;i--)
		{
			int t0=bit[0].ask(a[i]),t1=bit[1].ask(a[i]);if(t1==-1) t1=-INF;
			t0+=1+(cnt[i]-cnt[i+1]);t1+=1+(cnt[i]-cnt[i+1]);
			if((t0&1)==(t1&1)) bit[t1&1].change(a[i],max(t0,t1)),bit[(t1&1)^1].change(a[i],-INF);
			else bit[t0&1].change(a[i],t0),bit[t1&1].change(a[i],t1);
		}
		mi[0]=mi[1]=n+1;
		for(int i=1;i<=n;i++)
		{
			bit[0].gaygay(a[i]);bit[1].gaygay(a[i]);
			
			if(check(i,0)) ans.PB(0);
			else if(check(i,1)) ans.PB(1);
			else {puts("-1");return;}
		}
		for(int t=0;t<n;t++) putchar('0'+ans[t]);
	}
};
signed main()
{
	srand(time(0));
	mine::main();
}

Submission Info

Submission Time
Task E - High Elements
User Zory
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 2839 Byte
Status
Exec Time 289 ms
Memory 50408 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 1400 / 1400 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, subtask01-01.txt, subtask01-02.txt, subtask01-03.txt, subtask01-04.txt, subtask01-05.txt, subtask01-06.txt, subtask01-07.txt, subtask01-08.txt, subtask01-09.txt, subtask01-10.txt, subtask01-11.txt, subtask01-12.txt, subtask01-13.txt, subtask01-14.txt, subtask01-15.txt, subtask01-16.txt, subtask01-17.txt, subtask01-18.txt, subtask01-19.txt, subtask01-20.txt, subtask01-21.txt, subtask01-22.txt, subtask01-23.txt, subtask01-24.txt, subtask01-25.txt, subtask01-26.txt, subtask01-27.txt, subtask01-28.txt, subtask01-29.txt, subtask01-30.txt, subtask01-31.txt, subtask01-32.txt, subtask01-33.txt, subtask01-34.txt, subtask01-35.txt, subtask01-36.txt, subtask01-37.txt, subtask01-38.txt, subtask01-39.txt, subtask01-40.txt, subtask01-41.txt, subtask01-42.txt, subtask01-43.txt, subtask01-44.txt, subtask01-45.txt, subtask01-46.txt, subtask01-47.txt, subtask01-48.txt, subtask01-49.txt, subtask01-50.txt
Case Name Status Exec Time Memory
sample-01.txt 26 ms 23680 KB
sample-02.txt 25 ms 23680 KB
sample-03.txt 25 ms 23680 KB
sample-04.txt 25 ms 23680 KB
subtask01-01.txt 26 ms 23680 KB
subtask01-02.txt 121 ms 35680 KB
subtask01-03.txt 66 ms 30064 KB
subtask01-04.txt 52 ms 28032 KB
subtask01-05.txt 145 ms 38624 KB
subtask01-06.txt 144 ms 39776 KB
subtask01-07.txt 164 ms 43484 KB
subtask01-08.txt 29 ms 23936 KB
subtask01-09.txt 116 ms 36700 KB
subtask01-10.txt 78 ms 33120 KB
subtask01-11.txt 83 ms 34020 KB
subtask01-12.txt 65 ms 30964 KB
subtask01-13.txt 88 ms 34912 KB
subtask01-14.txt 96 ms 37212 KB
subtask01-15.txt 53 ms 29812 KB
subtask01-16.txt 29 ms 23936 KB
subtask01-17.txt 44 ms 27520 KB
subtask01-18.txt 112 ms 39776 KB
subtask01-19.txt 67 ms 33124 KB
subtask01-20.txt 44 ms 27520 KB
subtask01-21.txt 58 ms 30576 KB
subtask01-22.txt 49 ms 29168 KB
subtask01-23.txt 99 ms 34272 KB
subtask01-24.txt 208 ms 45784 KB
subtask01-25.txt 270 ms 50128 KB
subtask01-26.txt 245 ms 49120 KB
subtask01-27.txt 288 ms 50136 KB
subtask01-28.txt 273 ms 50408 KB
subtask01-29.txt 219 ms 49104 KB
subtask01-30.txt 204 ms 47832 KB
subtask01-31.txt 222 ms 49236 KB
subtask01-32.txt 229 ms 49236 KB
subtask01-33.txt 182 ms 48980 KB
subtask01-34.txt 168 ms 47580 KB
subtask01-35.txt 186 ms 48984 KB
subtask01-36.txt 183 ms 48984 KB
subtask01-37.txt 166 ms 48728 KB
subtask01-38.txt 146 ms 47584 KB
subtask01-39.txt 164 ms 48860 KB
subtask01-40.txt 161 ms 48856 KB
subtask01-41.txt 160 ms 49236 KB
subtask01-42.txt 141 ms 47976 KB
subtask01-43.txt 159 ms 48996 KB
subtask01-44.txt 150 ms 49112 KB
subtask01-45.txt 236 ms 49236 KB
subtask01-46.txt 217 ms 48592 KB
subtask01-47.txt 195 ms 48468 KB
subtask01-48.txt 146 ms 48728 KB
subtask01-49.txt 289 ms 50136 KB
subtask01-50.txt 241 ms 49628 KB