#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;
int tree[262144], lazy[262144];
void propagate(int i, int b, int e) {
if (!lazy[i]) return;
if (b != e) {
lazy[i * 2 + 1] = lazy[i];
lazy[i * 2 + 2] = lazy[i];
}
tree[i] = lazy[i];
lazy[i] = 0;
}
int query(int i, int b, int e, int l, int r) {
propagate(i, b, e);
if (r < b || e < l) return 0;
if (l <= b && e <= r) return tree[i];
int m = (b + e) / 2;
return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}
int update(int i, int b, int e, int l, int r, int v) {
propagate(i, b, e);
if (r < b || e < l) return tree[i];
if (l <= b && e <= r) {
lazy[i] = v;
propagate(i, b, e);
return tree[i];
}
int m = (b + e) / 2;
return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}
int n, m, x[100006], y[100006];
vector<int> adj[100006];
set<pair<int, int>> s;
vector<pair<int, int>> v;
int cl[100006];
void dfs(int x) {
for (auto &i: adj[x]) if (!cl[i]) {
cl[i] = -cl[x];
dfs(i);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d%d", x + i, y + i);
x[i]--, y[i]--;
if (x[i] > y[i]) s.insert({ i, 0 });
v.push_back({ x[i], -i - 1 });
v.push_back({ y[i], i });
}
sort(v.begin(), v.end());
int k = 0;
for (int i = 0; i < n; i++) {
while (k < (int)v.size() && v[k] < make_pair(i, 0)) {
if (v[k].second < 0) s.insert({ -v[k].second - 1, 0 });
else s.erase({ v[k].second, 0 });
k++;
}
if ((int)s.size() < 2) return puts("impossible"), 0;
if ((int)s.size() == 2) {
int first = s.begin()->first;
int second = next(s.begin())->first;
adj[first].push_back(second);
adj[second].push_back(first);
}
}
for (int i = 0; i < m; i++) if (!cl[i]) {
cl[i] = -1;
dfs(i);
}
for (int i = 0; i < m; i++) if (cl[i]) {
if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], cl[i]);
else update(0, 0, 131071, 0, y[i], cl[i]), update(0, 0, 131071, x[i], n - 1, cl[i]);
}
for (int i = 0; i < m; i++) if (!cl[i]) {
int t = 0;
if (x[i] <= y[i]) t = query(0, 0, 131071, x[i], y[i]);
else t = min(query(0, 0, 131071, 0, y[i]), query(0, 0, 131071, x[i], n - 1));
if (t >= 0) cl[i] = -1;
else cl[i] = 1;
if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], cl[i]);
else update(0, 0, 131071, 0, y[i], cl[i]), update(0, 0, 131071, x[i], n - 1, cl[i]);
}
s.clear();
for (int i = 0; i < m; i++) if (x[i] > y[i]) s.insert({ cl[i], i });
k = 0;
for (int i = 0; i < n; i++) {
while (k < (int)v.size() && v[k] < make_pair(i, 0)) {
if (v[k].second < 0) s.insert({ cl[-v[k].second - 1], -v[k].second - 1 });
else s.erase({ cl[v[k].second], v[k].second });
k++;
}
if (s.begin()->first == 1) return puts("impossible"), 0;
if (prev(s.end())->first == -1) return puts("impossible"), 0;
}
for (int i = 0; i < m; i++) {
if (cl[i] == -1) printf("0");
else printf("1");
}
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d%d", x + i, y + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
10984 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
'impossible' claimed, but there is a solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
