#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];
int find(int v) {
if(pai[v] == v) return v;
return pai[v] = find(pai[v]);
}
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 > b.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] = i;
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++) {
find(i);
// cout << i << " " << pai[i] << endl;
if(pai[i] == i) {
int a = vec[i].fr;
int b = vec[i].sc;
if(b >= a) {
segs.pb(mp(mp(a,b),i));
}
else {
segs.pb(mp(mp(a,b+n),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 << " " << x.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] == i) continue;
ans[i] = ans[pai[i]]^1;
}
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
}
else {
if(segs.size() == 1) {
ans[segs[0].sc] = 1;
for(int i = 0; i < m; i++) {
cout << ans[i];
}cout << endl;
return;
}
bool ok = false;
for(int i = 0; i+1 < segs.size(); i++) {
int l1 = segs[i].fr.fr;
int r1 = segs[i].fr.sc;
int l2 = segs[i+1].fr.fr;
int r2 = segs[i+1].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) {
//ultimo com o primeiro
int l1 = segs.back().fr.fr;
int r1 = segs.back().fr.sc;
int l2 = segs[0].fr.fr+n;
int r2 = segs[0].fr.sc+n;
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;
int i = 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;
}
}
if(ok == false) {
cout << "impossible" << endl;
return;
}
for(int i = 0; i < m; i++) {
if(pai[i] == i) 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 'void solve()':
alternating.cpp:102:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
102 | for(auto x : segs) {
| ^
alternating.cpp:106: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]
106 | for(int i = 0; i < segs.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:128:28: 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]
128 | for(int i = 0; i+1 < segs.size(); i++) {
| ~~~~^~~~~~~~~~~~~
alternating.cpp:146: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]
146 | for(int j = i; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:129:17: warning: unused variable 'l1' [-Wunused-variable]
129 | int l1 = segs[i].fr.fr;
| ^~
alternating.cpp:132:17: warning: unused variable 'r2' [-Wunused-variable]
132 | int r2 = segs[i+1].fr.sc;
| ^~
alternating.cpp:178: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]
178 | for(int j = i; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:162:17: warning: unused variable 'l1' [-Wunused-variable]
162 | int l1 = segs.back().fr.fr;
| ^~
alternating.cpp:165:17: warning: unused variable 'r2' [-Wunused-variable]
165 | int r2 = segs[0].fr.sc+n;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
487 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
487 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
487 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
551 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
487 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
