#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
void solve() {
int n, m;
cin >> n >> m;
array<int, 3> arr[m];
for (int i = 0; i < m; i++) {
cin >> arr[i][0] >> arr[i][1];
arr[i][0]--;
arr[i][1]--;
arr[i][2] = i;
}
sort(arr, arr + m, [&](const auto& a, const auto& b) -> bool {
if (a[0] != b[0]) {
return a[0] < b[0];
}
return a[1] > b[1];
});
int par[m];
pair<int, int> mx {-1, -1};
for (int i = 0; i < m; i++) {
auto [l, r, _] = arr[i];
dbg(i, l, r);
if (l > r) {
r += n;
}
if (r <= mx.first) {
par[i] = mx.second;
} else {
par[i] = i;
mx = {r, i};
}
}
for (int i = 0; i < m; i++) {
int u = i;
while (par[u] != u) {
u = par[u];
}
par[i] = u;
}
vector<int> vals;
int inds[m];
for (int i = 0; i < m; i++) {
if (par[i] == i) {
inds[i] = sz(vals);
vals.push_back(i);
}
dbg(i, par[i]);
}
auto covers_all = [&](const vector<pair<int, int>> &arr) -> bool {
vector<int> e[n];
for (auto& [l, r] : arr) {
e[l].push_back(r);
}
int mx = -1;
for (int i = 0; i < n; i++) {
for (auto& a : e[i]) {
mx = max(mx, a);
}
if (mx < i) {
return false;
}
}
return true;
};
auto check = [&](const vector<bool> &distr) -> void {
vector<pair<int, int>> segs[2];
auto add = [&](int i, int l, int r) -> void {
if (l > r) {
segs[i].emplace_back(l, n - 1);
segs[i].emplace_back(0, r);
} else {
segs[i].emplace_back(l, r);
}
};
bool ans[m];
for (auto& a : inds) {
a &= 1;
}
for (int i = 0; i < m; i++) {
auto &[l, r, ci] = arr[i];
if (par[i] == i) {
ans[ci] = distr[inds[i]];
} else {
ans[ci] = !distr[inds[par[i]]];
}
dbg(i, ans[ci]);
add(ans[ci], l, r);
}
if (covers_all(segs[0]) && covers_all(segs[1])) {
for (auto& a : ans) {
cout << a;
}
cout << endl;
exit(0);
}
};
int k = sz(vals);
if (k % 2 == 0 || k == 1) {
vector<bool> distr(k);
for (int i = 0; i < k; i++) {
distr[i] = i & 1;
}
check(distr);
cout << "impossible" << endl;
return;
}
for (int i = 0; i < k; i++) {
vector<bool> distr(k);
int j = i;
bool cur = false;
while (true) {
distr[j] = cur;
cur ^= true;
j = j + 1 == k ? 0 : j + 1;
if (j == i) {
break;
}
}
check(distr);
}
cout << "impossible" << endl;
return;
{
vector<pair<int, int>> cur;
for (auto& [l, r, _] : arr) {
if (l > r) {
cur.emplace_back(l, n - 1);
cur.emplace_back(0, r);
} else {
cur.emplace_back(l, r);
}
}
if (!covers_all(cur)) {
cout << "impossible" << endl;
return;
}
}
bool can[k];
vector<pair<int, int>> child[k];
for (int i = 0; i < m; i++) {
auto &[l, r, _] = arr[i];
if (par[i] != i) {
child[par[i]].emplace_back(l, r);
}
}
auto norm = [&](vector<pair<int, int>> &arr) -> void {
for (auto& [l, r] : arr) {
if (l > r) {
r += n;
}
}
};
for (int i = 0; i < k; i++) {
auto cl = child[i ? i - 1 : k - 1];
auto cr = child[i + 1 == k ? 0 : i + 1];
norm(cl);
norm(cr);
int mxl = -2, mnr = 1e9;
for (auto& [l, r] : cl) {
mxl = max(mxl, r);
}
for (auto& [l, r] : cr) {
mnr = min(mnr, l);
}
can[i] = mxl + 1 == mnr;
}
int cnt = 0;
for (auto& a : can) {
cnt += a;
}
for (int i = 0; i < k; i++) {
int j = i + 1 == k ? 0 : i + 1;
int ccnt = cnt - can[i] - can[j];
if (ccnt != k - 2) {
continue;
}
}
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin.exceptions(ios::failbit);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
7216 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
13 ms |
6220 KB |
Output is correct |
| 4 |
Correct |
20 ms |
6228 KB |
Output is correct |
| 5 |
Correct |
40 ms |
8144 KB |
Output is correct |
| 6 |
Execution timed out |
3057 ms |
8484 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
