Submission #70733

#TimeUsernameProblemLanguageResultExecution timeMemory
70733khohkoAlternating Current (BOI18_alternating)C++17
0 / 100
119 ms11604 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; #define ll long long #define pb push_back #define fr first #define sc second #define MAX ((ll)(1e12+100)) #define MX ((ll)(1e6+100)) #define ARRS ((ll)(2e6+100)) #define HS ((ll)(233)) #define MOD ((ll)(1e9+7)) #define EP ((double)(1e-9)) #define LG 21 #define mul(a,b) a=((a)*(b))%MOD using namespace std; ll n,m; pair<ll,pair<ll,ll> > a[ARRS]; ll pas[ARRS]; void eend(){ cout<<"impossible"; exit(0); } void rot(ll x){ for(int i=0; i<m; i++){ a[i].fr=(a[i].fr+n-1-x)%n+1; a[i].sc.fr=(a[i].sc.fr+n-1-x)%n+1; } } ll f[ARRS][2]; int main(){ #ifdef KHOKHO freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif // KHOKHO cin>>n>>m; pair<ll,ll> mx={-1,0}; for(int i=0; i<m; i++){ cin>>a[i].fr>>a[i].sc.fr; if(a[i].fr<=a[i].sc.fr) mx=max(mx,{a[i].sc.fr-a[i].fr,i}); else mx=max(mx,{n-(a[i].fr-a[i].sc.fr)+1,i}); a[i].sc.sc=i; } // cout<<mx.sc<<endl; rot(a[mx.sc].fr-1); // for(int i=0; i<m; i++){ // cout<<a[i].fr<<" "<<a[i].sc.fr<<endl; // } ll la=-MAX; vector<pair<ll,pair<ll,ll> > > v; for(int i=0; i<m; i++){ if(i==mx.sc)continue; if(a[i].fr>a[i].sc.fr) v.pb({a[i].fr,{n,i}}); else v.pb({a[i].fr,{a[i].sc.fr,i}}); } sort(v.begin(),v.end()); ll ma=0,mb=0,j=0; ma=a[mx.sc].sc.fr; multiset<pair<ll,ll> > st; bool e=1; for(int i=1; i<=n; i++){ while(j<v.size()&&v[j].fr==i)st.insert(v[j].sc),j++; while(st.size()&&st.begin()->fr<i)st.erase(st.begin()); if(ma<i){ if(!st.size()){ e=0; break; } ma=st.begin()->fr; pas[st.begin()->sc]=0; st.erase(st.begin()); } if(mb<i){ if(!st.size()){ e=0; break; } mb=st.begin()->fr; pas[st.begin()->sc]=1; st.erase(st.begin()); } } if(e){ for(int i=0; i<m; i++)cout<<pas[i]; return 0; } else for(int i=0; i<m; i++)pas[i]=0; // vector<pair<ll,pair<ll,ll> > > v; ll ld; pair<ll,ll> mk={-1,-1}; vector<ll> t; for(int i=0; i<m; i++){ if(i==mx.sc)continue; if(a[i].fr>a[i].sc.fr){ // v.pb({a[i].fr,{n,i}}); t.pb(i); mk=max({a[i].sc.fr,i},mk); } } for(auto ix:t){ mk.sc=ix; mk.fr=a[ix].sc.fr; ld=a[mk.sc].fr; //ld=MAX; pas[mk.sc]=1; v.clear(); // cout<<mk.fr<<" "<<mk.sc<<" "<<ld<<endl; for(int i=0; i<m; i++){ if(i==mx.sc)continue; if(i==mk.sc)continue; if(a[i].fr>a[i].sc.fr) v.pb({a[i].fr,{n,i}}); else v.pb({a[i].fr,{a[i].sc.fr,i}}); } sort(v.begin(),v.end()); // for(auto x:v){ // cout<<x.fr<<" - "<<x.sc.fr<<endl; // } ma=0,mb=0,j=0; ma=a[mx.sc].sc.fr; mb=mk.fr; //cout<<ma<<" "<<mb<<endl; st.clear(); e=1; for(int i=1; i<=n; i++){ while(j<v.size()&&v[j].fr==i)st.insert(v[j].sc),j++; while(st.size()&&st.begin()->fr<i)st.erase(st.begin()); // cout<<i<<" "<<ma<<" "<<mb<<" "<<st.size()<<endl; //if(ma>mb){ if(ma<i&&mb<i){ if(!st.size()){ e=0; break; } ma=(--st.end())->fr; pas[(--st.end())->sc]=0; st.erase((--st.end())); if(!st.size()){ e=0; break; } mb=st.begin()->fr; pas[st.begin()->sc]=1; st.erase(st.begin()); } else { if(i<ld&&mb<i){ if(!st.size()){ e=0; break; } mb=st.begin()->fr; pas[st.begin()->sc]=1; st.erase(st.begin()); } if(ma<i){ if(!st.size()){ e=0; break; } ma=st.begin()->fr; pas[st.begin()->sc]=0; st.erase(st.begin()); } } } if(e){ for(int i=0; i<m; i++)cout<<pas[i]; return 0; } } eend(); }

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:73:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<v.size()&&v[j].fr==i)st.insert(v[j].sc),j++;
         ~^~~~~~~~~
alternating.cpp:143:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<v.size()&&v[j].fr==i)st.insert(v[j].sc),j++;
          ~^~~~~~~~~
alternating.cpp:56:5: warning: unused variable 'la' [-Wunused-variable]
  ll la=-MAX;
     ^~
#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...