#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
int n, m, pai[maxn], ps[maxn], ans[maxn];
bool cmp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
if(a.fr.fr == b.fr.fr) {
return a.fr.sc > a.fr.sc;
}
return a.fr.fr < b.fr.fr;
}
void solve() {
cin >> n >> m;
vector<pair<pair<int,int>,int>> segs;
vector<pair<int,int>> vec;
for(int i = 0; i < m; i++) {
int a,b; cin >> a >> b;
vec.pb(mp(a,b));
pai[i] = -1;
if(b >= a) {
ps[a]++;
ps[b+1]--;
ps[a+n]++;
ps[b+n+1]--;
segs.pb(mp(mp(a,b),i));
segs.pb(mp(mp(a+n,b+n),i));
}
else {
ps[a]++;
ps[b+n+1]--;
ps[1]++;
ps[b+1]--;
ps[a+n]++;
ps[2*n+1]--;
segs.pb(mp(mp(a,b+n),i));
}
}
sort(all(segs),cmp); //menor L, maior R
priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int>>,greater<pair<pair<int,int>,int>>> pq;
for(auto X : segs) {
int l = X.fr.fr;
int r = X.fr.sc;
int id = X.sc;
// cout << l << " " << r << " " << id << endl;
while(pq.size() && pq.top().fr.sc < r) pq.pop();
if(pq.size() && pq.top().fr.fr <= l) {
pai[id] = pq.top().sc;
}
else {
pq.push(mp(mp(l,r),id));
}
}
segs.clear();
for(int i = 0; i < m; i++) {
if(pai[i] == -1) {
segs.pb(mp(vec[i],i));
}
}
sort(all(segs));
bool ok = true;
for(int i = 1; i <= 2*n; i++) {
ps[i]+=ps[i-1];
if(ps[i] < 2) ok = false;
}
if(!ok) {
cout << "impossible" << endl;
return;
}
for(auto x : segs) {
// cout << x.fr.fr << " " << x.fr.sc << endl;
}
if((((int) segs.size())&1) == 0) {
for(int i = 0; i < segs.size(); i++) {
int id = segs[i].sc;
ans[id] = i&1;
}
for(int i = 0; i < m; i++) {
if(pai[i] == -1) continue;
ans[i] = ans[pai[i]]^1;
}
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
}
else {
bool ok = false;
for(int i = 0; i < segs.size(); i++) {
int l1 = segs[i].fr.fr;
int r1 = segs[i].fr.sc;
int l2 = segs[(i+1)%((int)segs.size())].fr.fr;
int r2 = segs[(i+1)%((int)segs.size())].fr.sc;
//a area coberta por dois é l2 até r1
int l = l2;
int r = r1;
bool ok1 = true;
for(int i = l; i <= r; i++) {
if(ps[i] < 3) {
ok1 = false;
break;
}
}
if(ok1) {
int cnt = 0;
for(int j = i; j < segs.size(); j++) {
int id = segs[j].sc;
ans[id]=cnt;
cnt^=1;
}
for(int j = 0; j < i; j++) {
int id = segs[j].sc;
ans[id]=cnt;
cnt^=1;
}
ok = true;
break;
}
}
if(ok == false) {
cout << "impossible" << endl;
return;
}
for(int i = 0; i < m; i++) {
if(pai[i] == -1) continue;
ans[i] = ans[pai[i]]^1;
}
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
alternating.cpp: In function 'bool cmp(std::pair<std::pair<long long int, long long int>, long long int>, std::pair<std::pair<long long int, long long int>, long long int>)':
alternating.cpp:21:24: warning: self-comparison always evaluates to false [-Wtautological-compare]
21 | return a.fr.sc > a.fr.sc;
| ^
alternating.cpp: In function 'void solve()':
alternating.cpp:88:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
88 | for(auto x : segs) {
| ^
alternating.cpp:92:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 0; i < segs.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:107:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < segs.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:125:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int j = i; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:108:17: warning: unused variable 'l1' [-Wunused-variable]
108 | int l1 = segs[i].fr.fr;
| ^~
alternating.cpp:111:17: warning: unused variable 'r2' [-Wunused-variable]
111 | int r2 = segs[(i+1)%((int)segs.size())].fr.sc;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
'impossible' claimed, but there is a solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
'impossible' claimed, but there is a solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
'impossible' claimed, but there is a solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
10060 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1876 KB |
'impossible' claimed, but there is a solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
'impossible' claimed, but there is a solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
