#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5 + 10;
int n, m, k;
vector <int> s[N], g[N];
int color[N];
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
vector <tuple <int, int, int>> events;
set <int> s;
for (int i = 1; i <= m; ++i) {
int L, R;
cin >> L >> R;
if (L <= R) {
events.push_back({L, -1, i});
events.push_back({R, 1, i});
} else {
events.push_back({L, -1, i});
events.push_back({n, 1, i});
events.push_back({1, -1, i});
events.push_back({R, 1, i});
}
}
for (int i = 1; i <= n; ++i) events.push_back({i, 0, i});
sort(events.begin(), events.end());
set <int> c0, c1;
for (auto [x, sign, i]: events) {
if (sign == -1) {
s.insert(i);
} else if (sign == 1) {
s.erase(i);
} else {
if (s.size() < 2) {
cout << "impossible\n";
exit(0);
}
if (s.size() == 2) {
int u = *s.begin();
int v = *(--s.end());
g[u].push_back(v);
g[v].push_back(u);
// cout << u << ' ' << v << '\n';
}
}
}
function<int(int, int)> dfs = [&](int u, int c) {
if (color[u] != -1) return (int)(color[u] == c);
color[u] = c;
if (s.find(u) != s.end()) {
s.erase(u);
if (c == 0) c0.insert(u);
else c1.insert(u);
}
for (auto v: g[u])
if (!dfs(v, c ^ 1)) return 0;
return 1;
};
memset(color, -1, sizeof(color));
for (auto [x, sign, i]: events) {
if (sign == -1) {
if (color[i] == -1) s.insert(i);
else if (color[i] == 0) c0.insert(i);
else c1.insert(i);
} else if (sign == 1) {
s.erase(i);
c0.erase(i);
c1.erase(i);
} else {
if (c0.size() && c1.size()) continue;
if (c0.empty()) {
int u = *s.begin();
if (!dfs(u, 0)) {
cout << "impossible";
exit(0);
}
}
if (c1.empty()) {
int u = *s.begin();
if (!dfs(u, 0)) {
cout << "impossible";
exit(0);
}
}
}
}
for (int i = 1; i <= m; ++i) if (color[i] == -1) color[i] = 0;
for (int i = 1; i <= m; ++i) cout << color[i];
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | for (auto [x, sign, i]: events) {
| ^
alternating.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for (auto [x, sign, i]: events) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5400 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 |
3 ms |
5400 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 |
3 ms |
5400 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 |
119 ms |
14520 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 |
3 ms |
5400 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
