Submission #118056

#	Time	Username	Problem	Language	Result	Execution time	Memory
118056		samjia2000	Alternating Current (BOI18_alternating)	C++14	100 / 100	47 ms	10616 KiB

alternating

#include<bits/stdc++.h>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef double db;
typedef long long LL;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e5+5;

int n,m;
struct section{
	int l,r,id;
	section(const int l_=0,const int r_=0){l=l_;r=r_;}
}s[N],a[N],b[N];
int ka,kb;

bool cmp(section a,section b){return a.l!=b.l?a.l<b.l:a.r>b.r;}

int ans[N];
int Rig[N];
int to[N];
int lst[N],nxt[N];

int getlst(int x){return lst[x]==x?x:lst[x]=getlst(lst[x]);}

int getnxt(int x){return nxt[x]==x?x:nxt[x]=getnxt(nxt[x]);}

int be[N];
int cnt;

void update(int x){
	int l=getlst(x),r=getnxt(x);
	bool cg=0;
	int ll=(l+ka-2)%ka+1,rr=r%ka+1;
	if (cnt<ka-1&&getnxt(to[r])==getnxt(rr)){
		nxt[r]=rr;
		lst[rr]=r;
		cnt++;
		cg=1;
	}
	if (cnt<ka-1&&getlst(to[ll])==getlst(x)){
		lst[l]=ll;
		nxt[ll]=l;
		cnt++;
		cg=1;
	}
	if (cg)update(x);
}

int p1[N],p2[N];
int k1,k2;
int ad[N];

bool can(int k,section *a){
	fo(i,1,n+1)ad[i]=0;
	fo(i,1,k){
		if (a[i].r<=n){
			ad[a[i].l]++;
			ad[a[i].r+1]--;
		}
		else{
			ad[a[i].l]++;
			ad[n+1]--;
			ad[1]++;
			ad[a[i].r-n+1]--;
		}
	}
	fo(i,1,n)ad[i]+=ad[i-1];
	bool yes=1;
	fo(i,1,n)yes&=(ad[i]>0);
	return yes;
}

int main(){
//	freopen("data.in","r",stdin);
	n=get();m=get();
	int pm=m;
	fo(i,1,m){
		s[i].l=get();s[i].r=get();
		if (s[i].r<s[i].l)s[i].r+=n;
		s[i].id=i;
	}
	sort(s+1,s+1+m,cmp);
	int mx=0;
	int m_=0;
	fo(i,1,m)
	if (s[i].r<=mx)s[++m_]=s[i];
	else{
		mx=s[i].r;
		a[++ka]=s[i];
	}
	int w=1;
	for(;w<=ka&&a[w].r<=mx-n;w++)s[++m_]=a[w];
	w--;
	m=m_;
	fo(i,1,ka-w)a[i]=a[i+w];
	ka-=w;
	sort(s+1,s+1+m,cmp);
	mx=m_=0;
	fo(i,1,m)
	if(s[i].r<=mx)s[++m_]=s[i];
	else{
		mx=s[i].r;
		b[++kb]=s[i];
	}
	w=1;
	for(;w<=kb&&b[w].r<=mx-n;w++);
	w--;
	fo(i,1,kb-w)b[i]=b[i+w];
	kb-=w;
	if (!can(ka,a))return printf("impossible\n"),0;
	if(can(kb,b)){
		fo(i,1,pm)ans[i]=0;
		fo(i,1,ka)ans[a[i].id]=1;
		fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
		return 0;
	}
	fo(i,1,kb){
		b[kb+i]=b[i];
		b[kb+i].l+=n;
		b[kb+i].r+=n;
	}
	fd(i,kb*2,1){
		if (i==kb*2||b[i].r<b[i+1].l-1)Rig[i]=b[i].r;
		else Rig[i]=Rig[i+1];
	}
	fo(i,1,ka){
		int l=1,r=kb*2,w=-1;
		for(;l<=r;){
			int mid=(l+r)/2;
			if (b[mid].l-1<=a[i].r)w=mid,l=mid+1;
			else r=mid-1;
		}
		int p=a[i].r;
		if(w!=-1)p=max(p,Rig[w]);
		if (p>=n){
			to[i]=ka;
			l=1,r=ka,w=-1;
			for(;l<=r;){
				int mid=(l+r)/2;
				if (a[mid].l-1<=p-n)w=mid,l=mid+1;
				else r=mid-1;
			}
			if(w!=-1){
				w=min(w,i);
				to[i]=w;
			}
		}
		else{
			l=1,r=ka,w=-1;
			for(;l<=r;){
				int mid=(l+r)/2;
				if (a[mid].l-1<=p)w=mid,l=mid+1;
				else r=mid-1;
			}
			to[i]=w;
		}
	}
	fo(i,1,ka)lst[i]=nxt[i]=i;
	fo(i,1,ka)
	update(i);
	if (cnt==ka-1)return printf("impossible\n"),0;
	if ((ka-cnt)&1){
		bool yes=0;
		fo(i,1,ka){
			int x=getnxt(i);
			int y=getnxt(x%ka+1);
			y=getnxt(y%ka+1);
			if (getnxt(to[x])!=y){
				x=getnxt(x%ka+1);
				nxt[x]=x%ka+1;
				lst[x%ka+1]=x;
				yes=1;
				break;
			}
		}
		if (!yes)return printf("impossible\n"),0;
	}
	int x=getlst(1),now=1;
	for(;!be[x];){
		int y=getnxt(x)%ka+1;
		for(int p=x;p!=y;p=p%ka+1)be[p]=now;
		now=3-now;
		x=y;
	}
	fo(i,1,ka)if (be[i]==1)p1[++k1]=i;
	fo(i,1,k1){
		ans[a[p1[i]].id]=1;
		int x=p1[i],y=p1[i%k1+1];
		int now,pos;
		if (y>x&&a[x].r>=a[y].l-1)continue;
		if (x>y&&a[x].r-n>=a[y].l-1)continue;
		now=a[x].r;
		if (i<k1)pos=a[y].l-1;else pos=a[y].l+n-1;
	//	printf("%d\n",kb);
	//	fo(i,1,kb*2)printf("%d %d\n",b[i].l,b[i].r);
		for(;now<pos;){
			int l=1,r=kb*2,w=-1;
			for(;l<=r;){
				int mid=(l+r)/2;
				if (b[mid].l-1<=now)w=mid,l=mid+1;
				else r=mid-1;
			}
		//	printf("%d %d\n",now,w);
			now=b[w].r;
			ans[b[w].id]=1;
		}	
	}
	fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:3:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define fo(i,a,b) for(int i=a;i<=b;i++)
                   ^
alternating.cpp:131:3: note: in expansion of macro 'fo'
   fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
   ^~
alternating.cpp:131:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
                                 ^~~~~~~
alternating.cpp:3:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define fo(i,a,b) for(int i=a;i<=b;i++)
                   ^
alternating.cpp:225:2: note: in expansion of macro 'fo'
  fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
  ^~
alternating.cpp:225:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
                                ^~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26