Submission #63577

#TimeUsernameProblemLanguageResultExecution timeMemory
63577zetapiAlternating Current (BOI18_alternating)C++14
0 / 100
3005 ms9572 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #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)%M+1; int high=-1; 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,arr[cur].start+arr[cur].length-1); } return true; } 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 (stderr)

alternating.cpp: In function 'void Alternate()':
alternating.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<vec.size();A++)
              ~^~~~~~~~~~~
alternating.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<vec.size();A++)
              ~^~~~~~~~~~~
alternating.cpp: In function 'int main()':
alternating.cpp:162:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int A=0;A<vec.size();A++)
               ~^~~~~~~~~~~
alternating.cpp:174:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int A=0;A<vec.size();A++)
                 ~^~~~~~~~~~~
alternating.cpp:181:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int A=0;A<vec.size();A++)
                 ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...