#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 100000;
struct Seg {
int l, r, m, mn, lz;
Seg* ch[2];
Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), mn(0), lz(0) {
if (r - l > 1) {
ch[0] = new Seg(l, m);
ch[1] = new Seg(m, r);
}
}
void pull() {mn = min(ch[0]->mn, ch[1]->mn);}
void give(int v) {mn += v, lz += v;}
void push() {ch[0]->give(lz), ch[1]->give(lz), lz = 0;}
void add(int a, int b, int v) {
if (a <= l && r <= b) give(v);
else {
push();
if (a < m) ch[0]->add(a, b, v);
if (m < b) ch[1]->add(a, b, v);
pull();
}
}
int query(int a, int b) {
if (a <= l && r <= b) return mn;
push();
int ans = 1 << 30;
if (a < m) ans = min(ans, ch[0]->query(a, b));
if (m < b) ans = min(ans, ch[1]->query(a, b));
return ans;
}
};
int color[N];
bool odd_cycle;
vector <int> adj[N];
void dfs(int v) {
for (int u : adj[v]) {
if (!color[u]) {
color[u] = 3 ^ color[v];
dfs(u);
} else if (color[u] == color[v]) {
odd_cycle = true;
}
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <int> l(m), r(m);
vector <pii> event;
for (int i = 0; i < m; ++i) {
cin >> l[i] >> r[i], --l[i];
if (l[i] != r[i]) event.eb(l[i], i), event.eb(r[i], i);
if (l[i] >= r[i]) event.eb(0, i);
}
sort(all(event));
set <int> on;
for (int i = 0, j = 0; i < n; ++i) {
for (; j < event.size() && event[j].X == i; ++j) {
if (on.count(event[j].Y)) on.erase(event[j].Y);
else on.insert(event[j].Y);
}
if (on.size() < 2) return cout << "impossible\n", 0;
else if (on.size() == 2) {
int u = *on.begin(), v = *on.rbegin();
adj[u].pb(v), adj[v].pb(u);
}
}
for (int i = 0; i < m; ++i) if (!color[i] && !adj[i].empty()) {
color[i] = 1;
dfs(i);
}
if (odd_cycle) return cout << "impossible\n", 0;
Seg root(0, n);
auto add = [&](int i, int v) {
if (l[i] > r[i]) {
root.add(l[i], n, v);
root.add(0, r[i], v);
} else {
root.add(l[i], r[i], v);
}
};
auto qry = [&](int i) {
if (l[i] > r[i]) return min(root.query(l[i], n), root.query(0, r[i]));
return root.query(l[i], r[i]);
};
for (int i = 0; i < m; ++i) if (color[i] == 2) add(i, 1);
for (int i = 0; i < m; ++i) if (!color[i]) {
if (qry(i) == 1) color[i] = 2;
else color[i] = 1, add(i, -1);
}
for (int i = 0; i < m; ++i) cout << color[i] - 1;
cout << endl;
}
Compilation message
alternating.cpp: In constructor 'Seg::Seg(int, int)':
alternating.cpp:25:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), mn(0), lz(0) {
| ~~^~~
alternating.cpp: In function 'int main()':
alternating.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (; j < event.size() && event[j].X == i; ++j) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
20392 KB |
no wires in direction 1 between segments 1 and 100000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
