#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
vector<int> v[N];
int adjm[N][N], l[N], r[N], bit[N];
bool vis[N][N], in[N];
vector<int> adj[N];
int col[N], ans[N];
bool bipartite(int v, int c = 1) {
if (col[v]) return col[v] == c;
col[v] = c;
for (auto& x : adj[v]) {
if (!bipartite(x, 3 - c)) return false;
}
return true;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 0;i < m;i++) {
cin >> l[i] >> r[i];
l[i]--, r[i]--;
int nl = l[i], nr = r[i];
for (;nl != nr;nl = (nl + 1) % n) {
if ((int)v[nl].size() <= 2) v[nl].push_back(i);
}
if ((int)v[nr].size() <= 2) v[nr].push_back(i);
}
for (int i = 0;i < n;i++) {
if ((int)v[i].size() <= 1) {
cout << "impossible\n";
return 0;
}
}
for (int i = 0;i < n;i++) {
if ((int)v[i].size() == 2) {
in[v[i][0]] = in[v[i][1]] = 1;
adjm[v[i][0]][v[i][1]] = 1;
adjm[v[i][1]][v[i][0]] = 1;
}
}
for (int i = 0;i < m;i++) {
for (int j = 0;j < m;j++) {
if (adjm[i][j]) adj[i].push_back(j);
}
}
for (int i = 0;i < m;i++) {
if (in[i] && !col[i]) {
if (!bipartite(i)) {
cout << "impossible\n";
return 0;
}
}
int nl = l[i], nr = r[i];
for (;nl != nr;nl = (nl + 1) % n) {
bit[nl] |= col[i];
}
bit[nr] |= col[i];
}
memset(ans, -1, sizeof ans);
for (int i = 0;i < m;i++) {
if (in[i]) {
if (col[i] == 1) ans[i] = 0;
else ans[i] = 1;
continue;
} // OK
if (bit[l[i]] == 1) ans[i] = 1;
else if (bit[l[i]] == 2) ans[i] = 0;
}
for (int i = 0;i < m;i++) {
if (ans[i] != -1) continue;
int now = 3;
int nl = l[i], nr = r[i];
for (;nl != nr;nl = (nl + 1) % n) {
now &= bit[nl];
}
now &= bit[nr];
if (now == 1) ans[i] = 1;
else if (now == 2) ans[i] = 0;
else if (now == 3) ans[i] = 0;
else ans[i] = 0;
nl = l[i], nr = r[i];
for (;nl != nr;nl = (nl + 1) % n) {
bit[nl] |= (1 << ans[i]);
}
bit[nr] |= (1 << ans[i]);
}
for (int i = 0;i < m;i++) {
cout << ans[i];
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 33 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 35 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 33 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 35 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 43 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 46 |
Incorrect |
1 ms |
2396 KB |
no wires in direction 1 between segments 70 and 70 |
| 47 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 33 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 35 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 43 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 46 |
Incorrect |
1 ms |
2396 KB |
no wires in direction 1 between segments 70 and 70 |
| 47 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 33 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 35 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 43 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 46 |
Incorrect |
1 ms |
2396 KB |
no wires in direction 1 between segments 70 and 70 |
| 47 |
Halted |
0 ms |
0 KB |
- |
