#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 100000;
int main () {
srand(time(NULL));
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <pii> a(m);
vector <int> seg[n];
for (int i = 0, l, r; i < m; ++i) {
cin >> a[i].X >> a[i].Y, --a[i].X;
tie(l, r) = a[i];
if (l < r) {
for (int j = l; j < r; ++j) seg[j].pb(i);
} else {
for (int j = l; j < n; ++j) seg[j].pb(i);
for (int j = 0; j < r; ++j) seg[j].pb(i);
}
}
vector <vector <int>> adj(m);
for (int i = 0; i < n; ++i) {
if (seg[i].size() < 2) return cout << "impossible\n", 0;
if (seg[i].size() == 2) adj[seg[i][0]].pb(seg[i][1]), adj[seg[i][1]].pb(seg[i][0]);
}
vector <int> ans(m, -1);
bool odd_cycle = false;
function<void(int)> dfs = [&](int v) {
for (int u : adj[v]) {
if (ans[u] == -1) {
ans[u] = ans[v] ^ 1;
dfs(u);
} else if (ans[v] == ans[u]) {
odd_cycle = true;
}
}
};
for (int i = 0; i < m; ++i) if (ans[i] == -1 && !adj[i].empty()) {
ans[i] = 0;
dfs(i);
}
if (odd_cycle) return cout << "impossible\n", 0;
for (int i = 0; i < n; ++i) {
int ok = 0;
for (int j : seg[i]) {
if (ans[j] == -1) continue;
ok |= 1 << ans[j];
}
if (ok == 0) {
ans[seg[i][0]] = 0;
ans[seg[i][1]] = 1;
} else if (ok != 3) {
bool is = false;
for (int j : seg[i]) {
if (ans[j] == -1) continue;
ans[j] = ok == 2 ? 0 : 1;
is = true;
break;
}
if (is) return cout << "impossible\n", 0;
}
}
for (int i : ans) {
cout << (i == -1 ? 0 : i);
}
cout << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3144 ms |
807064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
'impossible' claimed, but there is a solution |
| 7 |
Halted |
0 ms |
0 KB |
- |
