#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++) {
// 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));
for(int i = 0; i < m; i++) {
if(pai[i] == i) continue;
int l1 = vec[i].fr;
int r1 = vec[i].sc;
//ve o ultimo com l menor ou igual a l1
auto it = lower_bound(all(segs),mp(mp(l1,inf),0LL));
int l2,r2,id;
l2 = it->fr.fr;
r2 = it->fr.sc;
id = it->sc;
//ve se da certo com esse
if(l1 >= l2 && r1 <= r2) {
pai[i] = id;
continue;
}
//tenta com l1+n e r1+n
l1+= n;
r1+= n;
it = lower_bound(all(segs),mp(mp(l1,inf),0LL));
l2,r2,id;
l2 = it->fr.fr;
r2 = it->fr.sc;
id = it->sc;
//ve se da certo com esse
if(l1 >= l2 && r1 <= r2) {
pai[i] = id;
continue;
}
}
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:111:9: warning: left operand of comma operator has no effect [-Wunused-value]
111 | l2,r2,id;
| ^~
alternating.cpp:111:15: warning: right operand of comma operator has no effect [-Wunused-value]
111 | l2,r2,id;
| ^~
alternating.cpp:111:17: warning: right operand of comma operator has no effect [-Wunused-value]
111 | l2,r2,id;
| ^
alternating.cpp:132:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
132 | for(auto x : segs) {
| ^
alternating.cpp:136: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]
136 | for(int i = 0; i < segs.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:158: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]
158 | for(int i = 0; i+1 < segs.size(); i++) {
| ~~~~^~~~~~~~~~~~~
alternating.cpp:176: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]
176 | for(int j = i; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:159:17: warning: unused variable 'l1' [-Wunused-variable]
159 | int l1 = segs[i].fr.fr;
| ^~
alternating.cpp:162:17: warning: unused variable 'r2' [-Wunused-variable]
162 | int r2 = segs[i+1].fr.sc;
| ^~
alternating.cpp:209: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]
209 | for(int j = i; j < segs.size(); j++) {
| ~~^~~~~~~~~~~~~
alternating.cpp:193:17: warning: unused variable 'l1' [-Wunused-variable]
193 | int l1 = segs.back().fr.fr;
| ^~
alternating.cpp:196:17: warning: unused variable 'r2' [-Wunused-variable]
196 | int r2 = segs[0].fr.sc+n;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
no wires in direction 1 between segments 12 and 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
no wires in direction 1 between segments 12 and 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
no wires in direction 1 between segments 12 and 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
9968 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
31 ms |
5592 KB |
Output is correct |
| 4 |
Correct |
27 ms |
5644 KB |
Output is correct |
| 5 |
Correct |
78 ms |
9736 KB |
Output is correct |
| 6 |
Correct |
79 ms |
9796 KB |
Output is correct |
| 7 |
Correct |
69 ms |
9704 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2224 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 10 |
Correct |
90 ms |
9912 KB |
Output is correct |
| 11 |
Correct |
55 ms |
9772 KB |
Output is correct |
| 12 |
Correct |
57 ms |
9824 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1856 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 15 |
Incorrect |
89 ms |
9712 KB |
no wires in direction 1 between segments 1 and 1 |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
no wires in direction 1 between segments 12 and 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
