#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
void no() {
cout << "impossible\n";
exit(0);
}
int ans[N];
vector<int> adj[N];
void dfs(int c, int b) {
ans[c] = b;
for (int nxt : adj[c]) {
if (ans[nxt] == -1) dfs(nxt, b ^ 1);
else if (ans[nxt] == b) no();
}
}
void solve() {
int n, m; cin >> n >> m;
vector<pair<int, int>> v(m);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b, --a, --b;
v[i] = {a, b};
}
vector<int> cnt(n);
auto add = [&](int l, int r) {
cnt[l]++;
if (r < n-1) cnt[r+1]--;
};
for (auto [l, r] : v) {
if (l <= r) {
add(l, r);
} else {
add(l, n-1);
add(0, r);
}
}
for (int i = 1; i < n; i++) cnt[i] += cnt[i-1];
if (*min_element(cnt.begin(), cnt.end()) < 2) {
no();
}
vector<int> use;
for (int i = 0; i < n; i++) {
if (cnt[i] == 2) {
use.push_back(i);
}
}
memset(ans, -1, sizeof(ans));
auto solve_hard = [&]() {
auto get_nxt = [&](int i) {
int idx = lower_bound(use.begin(), use.end(), i) - use.begin();
if (idx == sz(use)) return use[0];
return use[idx];
};
// cerr << "use: ";
// for (int x : use) cerr << x << ' ';
// cerr << endl;
vector<vector<int>> mine(n);
for (int i = 0; i < m; i++) {
auto [l, r] = v[i];
// cerr << "> " << l << ' ' << r << endl;
set<int> mark;
if (l <= r) {
int c = get_nxt(l);
while (!mark.count(c) && l <= c && c <= r) {
// cerr << c << ' ';
mark.insert(c);
c = get_nxt((c + 1) % n);
}
// cerr << endl << endl;
} else {
int c = get_nxt(l);
while (!mark.count(c) && (c >= l || c <= r)) {
// cerr << c << ' ';
mark.insert(c);
c = get_nxt((c + 1) % n);
}
// cerr << endl << endl;
}
for (int x : mark) {
mine[x].push_back(i);
}
}
for (int x : use) {
assert(sz(mine[x]) == 2);
int one = mine[x][0], two = mine[x][1];
adj[one].push_back(two);
adj[two].push_back(one);
}
for (int i = 0; i < m; i++) if (sz(adj[i]) && ans[i] == -1) {
dfs(i, 0);
}
};
if (sz(use)) solve_hard();
vector<int> one;
for (int i = 0; i < m; i++) {
if (ans[i] == 0 || ans[i] == -1) {
one.push_back(i);
}
}
auto reduce = [&]() { // clean one
vector<vector<ar<int, 3>>> ev(2 * n);
for (int x : one) {
auto [l, r] = v[x];
if (l <= r) {
ev[l].push_back({x, +1, r});
ev[r].push_back({x, -1, l});
ev[l + n].push_back({x, +1, r + n});
ev[r + n].push_back({x, -1, l + n});
} else {
ev[l].push_back({x, +1, r + n});
ev[r + n].push_back({x, -1, l});
}
}
set<int> bad;
set<pair<int, int>> open;
for (int i = 0; i < 2 * n; i++) {
for (auto [c, t, opp] : ev[i]) {
if (t == +1) {
open.emplace(i, c);
}
}
for (auto [c, t, opp] : ev[i]) {
if (t == -1) {
auto it = open.find({opp, c});
if (it != open.begin()) {
bad.insert(c);
}
}
}
for (auto [c, t, opp] : ev[i]) {
if (t == -1) {
open.erase({opp, c});
}
}
}
vector<int> new_one;
for (int x : one) if (!bad.count(x)) new_one.push_back(x);
swap(one, new_one);
};
reduce();
for (int x : one) {
ans[x] = 0;
}
vector<int> two;
for (int i = 0; i < m; i++) {
if (ans[i] != 0) {
ans[i] = 1;
two.push_back(i);
}
}
auto good = [&](vector<int> idx) { // check
vector<int> cnt_check(n);
auto add_check = [&](int l, int r) {
cnt_check[l]++;
if (r < n-1) cnt_check[r+1]--;
};
for (int x : idx) {
auto [l, r] = v[x];
if (l <= r) {
add_check(l, r);
} else {
add_check(l, n-1);
add_check(0, r);
}
}
for (int i = 1; i < n; i++) cnt_check[i] += cnt_check[i-1];
return *min_element(cnt_check.begin(), cnt_check.end()) > 0;
};
if (!good(one) || !good(two)) no();
for (int i = 0; i < m; i++) cout << ans[i];
cout << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
3164 KB |
'impossible' claimed, but there is a solution |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
3164 KB |
'impossible' claimed, but there is a solution |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
3164 KB |
'impossible' claimed, but there is a solution |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
24376 KB |
Output is correct |
| 2 |
Correct |
70 ms |
16304 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3932 KB |
Output is correct |
| 4 |
Correct |
59 ms |
20164 KB |
Output is correct |
| 5 |
Correct |
105 ms |
18984 KB |
Output is correct |
| 6 |
Correct |
15 ms |
5128 KB |
Output is correct |
| 7 |
Correct |
117 ms |
20412 KB |
Output is correct |
| 8 |
Incorrect |
28 ms |
11188 KB |
'impossible' claimed, but there is a solution |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
3164 KB |
'impossible' claimed, but there is a solution |
| 8 |
Halted |
0 ms |
0 KB |
- |
