Submission #63667

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63667	2018-08-02T12:47:34 Z	zetapi	Alternating Current (BOI18_alternating)	C++14	Compilation error	0 ms	0 KB

alternating

#include#include  <<bitsbits//stdcstdc++.++.hh>>
usingusing  namespacenamespace std std;;
  
#define#define pb  push_back pb  push_b
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
#define start  first
#define length second.first
 
typedef pair<int,int>  pii;
 
const int MAX=1e5;
 
bool cmp(const pair<int,pii> X,const pair<int,pii> Y)
{
	if(X.start==Y.start)
		return X.length>Y.length;
	return X.start<Y.start;
}
 
vector<pair<int,pii>> arr;
vector<int> vec,Enclosed[MAX];
 
int N,M,X,Y,par[MAX],mark[MAX];	
int len,cur,pre;
 
int root(int X)
{
	if(par[X]==X)
		return X;
	return par[X]=root(par[X]);
}
 
bool Subset(int X,int Y)
{
	int RelativeStart=(arr[X].start-arr[Y].start+N)%N;
	return RelativeStart+arr[X].length<=arr[Y].length;
}
 
void Alternate()
{
	for(int A=0;A<vec.size();A++)
		mark[arr[vec[A]].second.second]=A%2;
	for(int A=0;A<vec.size();A++)
	{
		for(auto B:Enclosed[vec[A]])
			mark[arr[B].second.second]=mark[arr[vec[A]].second.second]^1;
	}
	return ;
}
 
bool ok()
{
	int BIT[MAX];
	for(int A=0;A<2;A++)
	{
		for(int B=0;B<N;B++)
			BIT[B]=0;
		for(int B=0;B<M;B++)
		{
			if(mark[arr[B].second.second]!=A)
				continue;
			//cout<<"original index "<<B<<" start "<<arr[B].start<<"  length "<<arr[B].length<<"\n";
			if(arr[B].start+arr[B].length-1>=N)
			{
				BIT[0]++;
				BIT[arr[B].start]++;
				BIT[(arr[B].start+arr[B].length-1)%N+1]--;
			}
			else
			{
				BIT[arr[B].start]++;
				BIT[arr[B].start+arr[B].length]--;
			}	
		}
		for(int A=0;A<N;A++)
		{
			BIT[A+1]+=BIT[A];
			if(!BIT[A])
				return false;
		}
	}
	return true;
}
 
bool ok(int L,int R,int col)
{
	int Start=vec[L];
	int End=vec[R];
	int len=(End-Start+M-1)%M+1;
	int high=arr[Start].start;
	for(int A=0;A<len;A++)
	{
		int cur=(Start+A)%M;
		if(mark[arr[cur].second.second]!=col)
			continue;
		int now=arr[cur].start;
		if(cur<Start)
			now+=N;
		if(now>high)
			return false;
		high=max(high,now+arr[cur].length);
	}
	int now=arr[End].start;
	if(End<Start)
		now+=N;
	return now<=high;
}
 
void color(int X,int C)
{
	if(C>=0)
		mark[arr[vec[X]].second.second]=C;
	for(auto A:Enclosed[vec[X]])
		mark[arr[A].second.second]=!mark[arr[vec[X]].second.second];
	return ;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
 
	cin>>N>>M;
	for(int A=0;A<M;A++)
	{
		par[A]=A;
		cin>>X>>Y;
		X--;
		Y--;
		len=(Y-X+N)%N+1;
		arr.pb(mp(X,mp(len,A)));
	}	
	sort(arr.begin(),arr.end(),cmp);
	pre=0;
	for(int A=1;A<2*M;A++)
	{
		cur=A%M;
		if(Subset(cur,pre))
			par[cur]=pre;
		else
			pre=cur;	
	}
	for(int A=0;A<M;A++)
	{
		cur=root(A);
		if(A==cur)
			vec.pb(A);
		else
			Enclosed[cur].pb(A);
	}
	if(!(vec.size()%2))
	{
		Alternate();
		if(ok())
			for(int A=0;A<M;A++)
				cout<<mark[A];
		else
			cout<<"impossible\n";
		return 0;
	}
	else
	{
		for(int A=0;A<vec.size();A++)
		{
			int a=(A+0+vec.size())%vec.size();
			int b=(A+1+vec.size())%vec.size();
			int c=(A+2+vec.size())%vec.size();
			int d=(A+3+vec.size())%vec.size();	
			color(a,1);
			color(b,0);
			color(c,0);
			color(d,1);
			if(ok(a,d,1))
			{
				for(int A=0;A<vec.size();A++)
				{
					int cur=(d+A)%vec.size();
					if(cur==a or cur==b or cur==c or cur==d)
						continue;
					mark[arr[vec[cur]].second.second]=!mark[arr[vec[(cur-1+vec.size())%vec.size()]].second.second];
				}
				for(int A=0;A<vec.size();A++)
					color(A,-1);
				if(ok())
				{
					for(int A=0;A<M;A++)
						cout<<mark[A];
					return 0;
				}
				else
					cout<<"impossible";
				return 0;
			}
		}
	}
	cout<<"impossible";
	return 0;
}

Compilation message

alternating.cpp:2:9: error: #include expects "FILENAME" or <FILENAME>
 #include#include  <<bitsbits//stdcstdc++.++.hh>>
         ^
alternating.cpp:5:8: error: macro names must be identifiers
 #define#define pb  push_back pb  push_b
        ^
alternating.cpp:3:1: error: 'usingusing' does not name a type
 usingusing  namespacenamespace std std;;
 ^~~~~~~~~~
alternating.cpp:13:9: error: 'pair' does not name a type
 typedef pair<int,int>  pii;
         ^~~~
alternating.cpp:17:16: error: 'pair' does not name a type
 bool cmp(const pair<int,pii> X,const pair<int,pii> Y)
                ^~~~
alternating.cpp:17:20: error: expected ',' or '...' before '<' token
 bool cmp(const pair<int,pii> X,const pair<int,pii> Y)
                    ^
alternating.cpp: In function 'bool cmp(int)':
alternating.cpp:19:5: error: 'X' was not declared in this scope
  if(X.start==Y.start)
     ^
alternating.cpp:19:14: error: 'Y' was not declared in this scope
  if(X.start==Y.start)
              ^
alternating.cpp:21:9: error: 'X' was not declared in this scope
  return X.start<Y.start;
         ^
alternating.cpp:21:17: error: 'Y' was not declared in this scope
  return X.start<Y.start;
                 ^
alternating.cpp: At global scope:
alternating.cpp:24:1: error: 'vector' does not name a type
 vector<pair<int,pii>> arr;
 ^~~~~~
alternating.cpp:25:1: error: 'vector' does not name a type
 vector<int> vec,Enclosed[MAX];
 ^~~~~~
alternating.cpp: In function 'bool Subset(long long int, long long int)':
alternating.cpp:39:21: error: 'arr' was not declared in this scope
  int RelativeStart=(arr[X].start-arr[Y].start+N)%N;
                     ^~~
alternating.cpp: In function 'void Alternate()':
alternating.cpp:45:16: error: 'vec' was not declared in this scope
  for(int A=0;A<vec.size();A++)
                ^~~
alternating.cpp:46:8: error: 'arr' was not declared in this scope
   mark[arr[vec[A]].second.second]=A%2;
        ^~~
alternating.cpp:47:16: error: 'vec' was not declared in this scope
  for(int A=0;A<vec.size();A++)
                ^~~
alternating.cpp:49:14: error: 'Enclosed' was not declared in this scope
   for(auto B:Enclosed[vec[A]])
              ^~~~~~~~
alternating.cpp:50:9: error: 'arr' was not declared in this scope
    mark[arr[B].second.second]=mark[arr[vec[A]].second.second]^1;
         ^~~
alternating.cpp: In function 'bool ok()':
alternating.cpp:64:12: error: 'arr' was not declared in this scope
    if(mark[arr[B].second.second]!=A)
            ^~~
alternating.cpp:67:7: error: 'arr' was not declared in this scope
    if(arr[B].start+arr[B].length-1>=N)
       ^~~
alternating.cpp: In function 'bool ok(long long int, long long int, long long int)':
alternating.cpp:91:12: error: 'vec' was not declared in this scope
  int Start=vec[L];
            ^~~
alternating.cpp:94:11: error: 'arr' was not declared in this scope
  int high=arr[Start].start;
           ^~~
alternating.cpp:105:8: error: 'max' was not declared in this scope
   high=max(high,now+arr[cur].length);
        ^~~
alternating.cpp:105:8: note: suggested alternative: 'mark'
   high=max(high,now+arr[cur].length);
        ^~~
        mark
alternating.cpp: In function 'void color(long long int, long long int)':
alternating.cpp:116:8: error: 'arr' was not declared in this scope
   mark[arr[vec[X]].second.second]=C;
        ^~~
alternating.cpp:116:12: error: 'vec' was not declared in this scope
   mark[arr[vec[X]].second.second]=C;
            ^~~
alternating.cpp:117:13: error: 'Enclosed' was not declared in this scope
  for(auto A:Enclosed[vec[X]])
             ^~~~~~~~
alternating.cpp:117:22: error: 'vec' was not declared in this scope
  for(auto A:Enclosed[vec[X]])
                      ^~~
alternating.cpp:118:8: error: 'arr' was not declared in this scope
   mark[arr[A].second.second]=!mark[arr[vec[X]].second.second];
        ^~~
alternating.cpp: In function 'int main()':
alternating.cpp:124:2: error: 'ios_base' has not been declared
  ios_base::sync_with_stdio(false);
  ^~~~~~~~
alternating.cpp:126:2: error: 'cin' was not declared in this scope
  cin>>N>>M;
  ^~~
alternating.cpp:126:2: note: suggested alternative: 'main'
  cin>>N>>M;
  ^~~
  main
alternating.cpp:134:3: error: 'arr' was not declared in this scope
   arr.pb(mp(X,mp(len,A)));
   ^~~
alternating.cpp:6:13: error: 'make_pair' was not declared in this scope
 #define mp  make_pair
             ^
alternating.cpp:134:15: note: in expansion of macro 'mp'
   arr.pb(mp(X,mp(len,A)));
               ^~
alternating.cpp:6:13: error: 'make_pair' was not declared in this scope
 #define mp  make_pair
             ^
alternating.cpp:134:10: note: in expansion of macro 'mp'
   arr.pb(mp(X,mp(len,A)));
          ^~
alternating.cpp:136:7: error: 'arr' was not declared in this scope
  sort(arr.begin(),arr.end(),cmp);
       ^~~
alternating.cpp:136:2: error: 'sort' was not declared in this scope
  sort(arr.begin(),arr.end(),cmp);
  ^~~~
alternating.cpp:136:2: note: suggested alternative: 'short'
  sort(arr.begin(),arr.end(),cmp);
  ^~~~
  short
alternating.cpp:150:4: error: 'vec' was not declared in this scope
    vec.pb(A);
    ^~~
alternating.cpp:152:4: error: 'Enclosed' was not declared in this scope
    Enclosed[cur].pb(A);
    ^~~~~~~~
alternating.cpp:154:7: error: 'vec' was not declared in this scope
  if(!(vec.size()%2))
       ^~~
alternating.cpp:159:5: error: 'cout' was not declared in this scope
     cout<<mark[A];
     ^~~~
alternating.cpp:159:5: note: suggested alternative: 'root'
     cout<<mark[A];
     ^~~~
     root
alternating.cpp:161:4: error: 'cout' was not declared in this scope
    cout<<"impossible\n";
    ^~~~
alternating.cpp:161:4: note: suggested alternative: 'root'
    cout<<"impossible\n";
    ^~~~
    root
alternating.cpp:190:7: error: 'cout' was not declared in this scope
       cout<<mark[A];
       ^~~~
alternating.cpp:190:7: note: suggested alternative: 'root'
       cout<<mark[A];
       ^~~~
       root
alternating.cpp:194:6: error: 'cout' was not declared in this scope
      cout<<"impossible";
      ^~~~
alternating.cpp:194:6: note: suggested alternative: 'root'
      cout<<"impossible";
      ^~~~
      root
alternating.cpp:199:2: error: 'cout' was not declared in this scope
  cout<<"impossible";
  ^~~~
alternating.cpp:199:2: note: suggested alternative: 'root'
  cout<<"impossible";
  ^~~~
  root