Submission #131870

#TimeUsernameProblemLanguageResultExecution timeMemory
131870TadijaSebezAlternating Current (BOI18_alternating)C++11
0 / 100
3065 ms31900 KiB
#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 (stderr)

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]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...