oj.uz

Submission #131870

# Submission time Handle Problem Language Result Execution time Memory
131870 2019-07-17T20:37:53 Z TadijaSebez Alternating Current (BOI18_alternating) C++11
0 / 100
 3000 ms 31900 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
int l[N],r[N],n,m;
int GetMax()
{
	int mx=-1,sz=-1;
	for(int i=1;i<=m;i++)
	{
		int tmp=r[i]-l[i]+1;
		if(l[i]>r[i]) tmp=n-l[i]+1+r[i];
		if(tmp>sz) sz=tmp,mx=i;
	}
	return mx;
}
void Rotate(int x)
{
	for(int i=1;i<=m;i++)
	{
		l[i]-=x-1;if(l[i]<=0) l[i]+=n;
		r[i]-=x-1;if(r[i]<=0) r[i]+=n;
	}
}
int sum[N];
bool bad[N];
bool use[N];
vector<int> all[N];
bool Check(int x)
{
	for(int i=1;i<=n;i++) sum[i]=0;
	int cur=0;
	for(int i=1;i<=m;i++) if(use[i]==x)
	{
		sum[l[i]]++;
		if(r[i]>n) sum[r[i]-n+1]--,cur++;
		else sum[r[i]+1]--;
	}
	for(int i=1;i<=n;i++)
	{
		cur+=sum[i];
		if(cur==0) return 0;
	}
	return 1;
}
vector<int> v[N],E[N];
set<pair<int,int>> edges;
bool dp[N];
int go[N];
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++) scanf("%i %i",&l[i],&r[i]);
	int fir=GetMax();
	Rotate(l[fir]);
	int cur=0;
	for(int i=1;i<=m;i++)
	{
		sum[r[i]+1]--;
		sum[l[i]]++;
		if(l[i]>r[i]) cur++;
	}
	vector<int> pos;
	for(int i=1;i<=n;i++)
	{
		cur+=sum[i];
		if(cur<2) return 0*printf("impossible\n");
		if(cur==2) bad[i]=1,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();
			int j=L;
			do
			{
				v[j].pb(i);
				j=(j+1)%pos.size();
			}while(j!=R);
		}
		for(int j=0;j<pos.size();j++)
		{
			E[v[j][0]].pb(v[j][1]);
			E[v[j][1]].pb(v[j][0]);
			edges.insert({v[j][0],v[j][1]});
			edges.insert({v[j][1],v[j][0]});
		}
	}
	dp[fir]=1;
	for(int i=1;i<=m;i++)
	{
		if(r[i]<l[i]) r[i]+=n;
		if(r[i]>r[fir])
		{
			all[r[i]].pb(i);
		}
	}
	for(int i=r[fir]+1;i<2*n;i++)
	{
		for(int seg:all[i])
		{
			for(int j=1;j<=m;j++) if(r[j]<r[seg] && dp[j])
			{
                if(l[seg]<=r[j]+1 && !edges.count({seg,j}))
				{
					if(!dp[seg] || r[j]<r[go[seg]]) go[seg]=j;
					dp[seg]=1;
				}
			}
		}
	}
	int p=-1;
	for(int i=1;i<=m;i++) if(dp[i] && r[i]>=n && !edges.count({fir,i})) p=i;
	if(p==-1) return 0*printf("impossible\n");
	while(p) use[p]=1,p=go[p];
	use[fir]=0;
	if(!Check(1)) use[fir]=1;
	for(int i=1;i<=m;i++) printf("%i",use[i]);
	return 0;
}

Compilation message

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 15 ms 14428 KB Output is correct
6 Incorrect 14 ms 14456 KB no wires in direction 0 between segments 1 and 2
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 15 ms 14428 KB Output is correct
6 Incorrect 14 ms 14456 KB no wires in direction 0 between segments 1 and 2
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 15 ms 14428 KB Output is correct
6 Incorrect 14 ms 14456 KB no wires in direction 0 between segments 1 and 2
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15712 KB Output is correct
2 Correct 34 ms 19696 KB Output is correct
3 Correct 27 ms 15208 KB Output is correct
4 Correct 38 ms 16288 KB Output is correct
5 Execution timed out 3065 ms 31900 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 15 ms 14428 KB Output is correct
6 Incorrect 14 ms 14456 KB no wires in direction 0 between segments 1 and 2
7 Halted 0 ms 0 KB -