#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];
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;
vector<pair<ll,pair<ll,ll> > > v1;
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;
}
// 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;
for(int i=0; i<m; i++)pas[i]=0;
pas[mk.sc]=1;
v.clear();
v1.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}}),
v1.pb({n,{a[i].fr,i}});
else
v.pb({a[i].fr,{a[i].sc.fr,i}}),
v1.pb({a[i].sc.fr,{a[i].fr,i}});
}
sort(v.begin(),v.end());
sort(v1.begin(),v1.end());
// reverse(v1.begin(),v1.end());
ll la=a[mx.sc].sc.fr,lb=mk.fr,ra=n+1,rb=a[mk.sc].fr;
ll i=0,j=v1.size()-1;
set<pair<ll,ll> > sa;
set<pair<ll,ll> > sb;
ll e=1;
while(min(la,lb)+1<max(ra,rb)){
//cout<<la<<" "<<lb<<" "<<ra<<" "<<rb<<endl;
while(i<v.size()&&v[i].fr<=min(la,lb)+1){
sa.insert(v[i].sc);
i++;
}
while(j>=0&&v1[j].fr>=max(ra,rb)-1){
sb.insert(v1[j].sc);
j--;
}
if(!sa.size()&&!sb.size()){e=0;break;}
if(la==lb){
while(sb.size()&&f[(--sb.end())->sc])sb.erase((--sb.end()));
if(sb.size()){
if(ra<=rb){
rb=(--sb.end())->fr;
pas[(--sb.end())->sc]=1;
f[(--sb.end())->sc]=1;
sb.erase((--sb.end()));
}
else {
ra=(--sb.end())->fr;
pas[(--sb.end())->sc]=0;
f[(--sb.end())->sc]=1;
sb.erase((--sb.end()));
}
}
}
while(sa.size()&&f[sa.begin()->sc])sa.erase(sa.begin());
if(sa.size()){
if(la>=lb){
lb=sa.begin()->fr;
pas[sa.begin()->sc]=1;
f[sa.begin()->sc]=1;
sa.erase(sa.begin());
}
else {
la=sa.begin()->fr;
pas[sa.begin()->sc]=0;
f[sa.begin()->sc]=1;
sa.erase(sa.begin());
}
}
while(sb.size()&&f[(--sb.end())->sc])sb.erase((--sb.end()));
if(sb.size()){
if(ra<=rb){
rb=(--sb.end())->fr;
pas[(--sb.end())->sc]=1;
f[(--sb.end())->sc]=1;
sb.erase((--sb.end()));
}
else {
ra=(--sb.end())->fr;
pas[(--sb.end())->sc]=0;
f[(--sb.end())->sc]=1;
sb.erase((--sb.end()));
}
}
if(la+1>=ra)la=n+1,ra=0;
if(lb+1>=rb)lb=n+1,rb=0;
}
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:74: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:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<v.size()&&v[i].fr<=min(la,lb)+1){
~^~~~~~~~~
alternating.cpp:56:5: warning: unused variable 'la' [-Wunused-variable]
ll la=-MAX;
^~
alternating.cpp:102:5: warning: variable 'ld' set but not used [-Wunused-but-set-variable]
ll ld;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
416 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
416 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
416 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
11472 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11472 KB |
Output is correct |
| 3 |
Correct |
59 ms |
11472 KB |
Output is correct |
| 4 |
Correct |
76 ms |
11472 KB |
Output is correct |
| 5 |
Correct |
162 ms |
11472 KB |
Output is correct |
| 6 |
Correct |
252 ms |
11472 KB |
Output is correct |
| 7 |
Correct |
154 ms |
11472 KB |
Output is correct |
| 8 |
Incorrect |
7 ms |
11472 KB |
'impossible' claimed, but there is a solution |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
416 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
