#include <bits/stdc++.h>
int main() {
// input
int N, M;
std::cin >> N >> M;
std::vector<int> A(M), B(M);
for (int i = 0; i < M; ++i) {
std::cin >> A[i] >> B[i];
--A[i];
if (A[i] >= B[i]) {
B[i] += N;
}
}
// calc root
std::vector<int> root(M, -1);
std::vector<std::vector<int>> in(2 * N);
for (int i = 0; i < M; ++i) {
in[A[i]].push_back(i);
in[A[i] + N].push_back(i);
}
std::pair<int, int> max_right = {-1, 0};
for (int i = 0; i < 2 * N; ++i) {
// reverse-sort
std::sort(in[i].begin(), in[i].end(), [&](const int a, const int b) {
int r1 = B[a], r2 = B[b];
while (r1 <= i) {
r1 += N;
}
while (r2 <= i) {
r2 += N;
}
return r1 > r2;
});
for (const int e : in[i]) {
int l = i, r = B[e];
while (r <= l) {
r += N;
}
if (r < max_right.first) {
root[e] = max_right.second;
} else {
max_right.first = r;
max_right.second = e;
}
}
}
for (int i = 0; i < M; ++i) {
auto rec = [&](auto &&self, const int v) {
if (root[v] == -1) {
return v;
} else {
return root[v] = self(self, root[v]);
}
};
rec(rec, i);
}
std::vector<int> roots;
for (int i = 0; i < M; ++i) {
if (root[i] == -1) {
roots.push_back(root[i] = i);
}
}
std::sort(roots.begin(), roots.end(), [&](const int a, const int b) {
return A[a] < A[b];
});
const int K = (int)roots.size();
std::vector<int> reorder(N, -1);
for (int i = 0; i < K; ++i) {
reorder[roots[i]] = i;
}
// calc limit
auto calc_time = [&](const std::vector<int> roots,
const std::vector<std::vector<int>> od) {
std::vector<int> time_x(N, K), time_y(N, K);
std::set<int> bad_x, bad_y;
for (int i = 0; i < N; ++i) {
bad_x.insert(i);
bad_y.insert(i);
}
auto fill = [&](std::set<int> &s, std::vector<int> &tiv, const int i, const int t) {
auto itr = s.lower_bound(A[i]);
while (itr != s.end() and *itr < B[i]) {
tiv[*itr] = t;
itr = s.erase(itr);
}
itr = s.begin();
while (itr != s.end() and *itr < B[i] - N) {
tiv[*itr] = t;
itr = s.erase(itr);
}
};
for (int i = 0; i < K; ++i) {
const bool is_x = i % 2 == 0;
fill(is_x ? bad_x : bad_y, is_x ? time_x : time_y, roots[i], i);
for (const int e : od[i]) {
fill(is_x ? bad_y : bad_x, is_x ? time_y : time_x, e, i);
}
}
return std::make_pair(time_x, time_y);
};
std::vector<std::vector<int>> od(K);
for (int i = 0; i < M; ++i) {
if (root[i] == i) {
continue;
}
od[reorder[root[i]]].push_back(i);
}
const auto [time_x1, time_y1] = calc_time(roots, od);
std::reverse(roots.begin(), roots.end());
std::reverse(od.begin(), od.end());
auto [time_y2, time_x2] = calc_time(roots, od);
for (auto &e : time_x2) {
e = K - e;
}
for (auto &e : time_y2) {
e = K - e;
}
// skip
int ma = -1;
for (const int e : time_x1) {
ma = std::max(ma, e);
}
for (const int e : time_y1) {
ma = std::max(ma, e);
}
if (ma != K) {
for (int i = 0; i < M; ++i) {
bool answer = root[i] == i;
answer ^= reorder[root[i]] % 2 == 1;
std::cout << answer;
}
std::cout << std::endl;
return 0;
}
// solve
std::set<int> ok_pos;
for (int i = 1; i < K; ++i) {
ok_pos.insert(i);
}
for (int i = 0; i < N; ++i) {
auto erase = [&](const std::vector<int> &t1, const std::vector<int> &t2) {
const int l = t2[i], r = t1[i];
auto itr = ok_pos.lower_bound(l);
while (itr != ok_pos.end() and *itr < r) {
itr = ok_pos.erase(itr);
}
};
erase(time_x1, time_x2);
erase(time_y1, time_y2);
}
// output
if (ok_pos.empty()) {
std::cout << "impossible" << std::endl;
} else {
const int p = *ok_pos.rbegin();
for (int i = 0; i < M; ++i) {
bool answer = root[i] == i;
answer ^= reorder[root[i]] >= p;
answer ^= reorder[root[i]] % 2 == 1;
std::cout << answer;
}
std::cout << std::endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
308 KB |
no wires in direction 1 between segments 1 and 2 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
308 KB |
no wires in direction 1 between segments 1 and 2 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
308 KB |
no wires in direction 1 between segments 1 and 2 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
24212 KB |
Output is correct |
| 2 |
Correct |
95 ms |
16320 KB |
Output is correct |
| 3 |
Correct |
128 ms |
20944 KB |
Output is correct |
| 4 |
Correct |
129 ms |
20996 KB |
Output is correct |
| 5 |
Correct |
207 ms |
27364 KB |
Output is correct |
| 6 |
Incorrect |
231 ms |
26296 KB |
no wires in direction 0 between segments 26258 and 26258 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
308 KB |
no wires in direction 1 between segments 1 and 2 |
| 6 |
Halted |
0 ms |
0 KB |
- |
