#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};
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}});
mk=max({a[i].sc.fr,i},mk);
}
}
ld=a[mk.sc].fr;
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(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
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:136: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:56:5: warning: unused variable 'la' [-Wunused-variable]
ll la=-MAX;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
560 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
560 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
560 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
11480 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11480 KB |
Output is correct |
| 3 |
Incorrect |
64 ms |
11480 KB |
no wires in direction 1 between segments 1 and 100000 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
560 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
