Submission #130095

#	Time	Username	Problem	Language	Result	Execution time	Memory
130095		TadijaSebez	Alternating Current (BOI18_alternating)	C++11	0 / 100	148 ms	18028 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
int sum[N],l[N],r[N],sz[N];
int x[N],y[N];
vector<int> E[N],all[N][2];
int ans[N],n;
bool in(int x, int y)
{
	return (l[y]<=l[x] && r[y]>=r[x]) || (l[y]<=l[x]+n && r[y]>=r[x]+n);
}
int main()
{
	int m;
	scanf("%i %i",&n,&m);
	int fir=-1,cur=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%i %i",&l[i],&r[i]);
		sz[i]=r[i]-l[i]+1;
		if(l[i]>r[i]) sz[i]=n-l[i]+1+r[i];
		//if(l[i]>r[i] || l[i]==1) fir=i;
		if(fir==-1 || sz[i]>sz[fir]) fir=i;
	}
	int lf=l[fir];
	//printf("%i %i\n",fir,lf);
	for(int i=1;i<=m;i++)
	{
		l[i]--;r[i]--;
		l[i]-=lf-1;
		r[i]-=lf-1;
        l[i]+=2*n;
        r[i]+=2*n;
        l[i]%=n;
        r[i]%=n;
        l[i]++;
        r[i]++;
        //printf("%i %i\n",l[i],r[i]);
	}
	for(int i=1;i<=m;i++)
	{
		sum[l[i]]++;
		sum[r[i]+1]--;
		if(l[i]>r[i])
		{
			cur++;
			all[l[i]][0].pb(i);
		}
		else all[l[i]][1].pb(i);
	}
	vector<int> pos;
	for(int i=1;i<=n;i++)
	{
		cur+=sum[i];
		if(cur<2) return 0*printf("impossible\n");
		if(cur==2) pos.pb(i);
	}
	if(pos.size())
	{
		for(int i=1;i<=m;i++)
		{
			int L=lower_bound(pos.begin(),pos.end(),l[i])-pos.begin();
			int R=upper_bound(pos.begin(),pos.end(),r[i])-pos.begin();
			L%=pos.size();
			R%=pos.size();
			for(int j=L;j!=R;j=(j+1)%pos.size()) y[j]=x[j],x[j]=i;
		}
		for(int j=0;j<pos.size();j++)
		{
			E[x[j]].pb(y[j]);
			E[y[j]].pb(x[j]);
		}
	}
	stack<int> st;
	if(l[fir]>r[fir])
	{
		for(int i=l[fir]+1;i<=n;i++) for(int j:all[i][0]) st.push(j);
	}
	vector<int> segs;
	segs.pb(fir);
	for(int i=1;i<=r[fir]+1;i++) for(int j:all[i][1]) st.push(j);
	int R=r[fir],L=(l[fir]-2+n)%n+1;
	//printf("%i\n",fir);
	for(int i=1;i<=m;i++) if(l[i]>r[i]) r[i]+=n;
	while(R<L)
	{
		while(st.size() && r[st.top()]<=R) st.pop();
		if(st.empty()) return 0*printf("impossible\n");
		int s=st.top();
		while(segs.size()>1 && in(segs.back(),s)) segs.pop_back();
		segs.pb(s);
		//printf("%i\n",s);
		if(r[s]>=L) break;
		while(R<=r[s])
		{
			for(int j:all[R+1][1]) st.push(j);
			R++;
		}
		R=r[s];
	}
	for(int s:segs)
	{
		ans[s]=1;
		for(int t:E[s]) if(ans[t]) return 0*printf("impossible\n");
	}
	for(int i=1;i<=m;i++) printf("%i",ans[i]);
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<pos.size();j++)
               ~^~~~~~~~~~~
alternating.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
alternating.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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