#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e5+10;
int pref[maxn];
int mx = 0, ini_mx = 0, n, m;
struct Wire {
int l, r, id;
int sz() const { return r >= l ? r - l + 1 : r + (n - l + 1); }
bool operator<(const Wire& o) const {
if(l == o.l) return this->sz() > o.sz();
if((l >= ini_mx) == (o.l >= ini_mx)) return l < o.l; // retorno o que tem o menor l já que eles são da mesma metade
return l > o.l; // já que eles são de metades diferentes eu retorno o que tiver na metade maior
}
} wr[maxn];
int pai[maxn];
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d %d", &wr[i].l, &wr[i].r); wr[i].id = i;
if(wr[i].l <= wr[i].r) {
pref[wr[i].l]++;
pref[wr[i].r+1]--;
} else {
pref[wr[i].l]++;
pref[1]++;
pref[wr[i].r+1]--;
}
if(wr[i].sz() > mx) {
mx = wr[i].sz();
ini_mx = wr[i].l;
}
}
for(int i = 1; i <= n; i++)
pref[i] += pref[i-1];
for(int i = n+1; i <= 2*n; i++) {
pref[i] = pref[i-n];
if(pref[i] < 2) return puts("impossible"), 0;
}
sort(wr, wr+m);
for(int i = 0; i < m; i++)
if(wr[i].l < ini_mx) wr[i].l += n, wr[i].r += n, assert(wr[i].l <= wr[i].r);
else if(wr[i].r < ini_mx) assert(wr[i].r < wr[i].l), wr[i].r += n;
int fim = 0, aberto = 0;
vector<Wire> brabos;
memset(pai, -1, sizeof pai);
for(int i = 0; i < m; i++) {
auto [l, r, id] = wr[i];
if(r > fim) brabos.push_back(wr[i]), aberto = id, fim = r;
else pai[id] = aberto;
}
vector<int> ans(m);
if(((brabos.size() & 1) ^ 1) || brabos.size() == 1) {
for(int i = 0; i < brabos.size(); i++)
ans[brabos[i].id] = i&1;
for(int i = 0; i < m; i++)
if(pai[i] != -1) ans[i] = 1^ans[pai[i]];
for(int i = 0; i < m; i++)
printf("%d", ans[i]);
puts("");
return 0;
}
brabos.push_back(brabos.front());
int r_a = -1;
for(int i = 0; i < brabos.size(); i++) {
auto [l, r, id] = brabos[i];
if(r_a != -1) {
bool tem = pref[r_a] >= 3;
static int cnt = 0;
for(int j = l; j != (r_a-1)%n + 1; j = (j%n)+1)
tem &= pref[j] >= 3;
if(l == ((r_a)%n+1) || tem) {
brabos.pop_back();
if(i == brabos.size()) i = 0;
auto nxt = [&](int x) { return x%brabos.size()+1; };
ans[brabos[i].id] = 1;
for(int k = i+1, opa = 0; k != i; k = nxt(k), opa ^= 1)
ans[brabos[k].id] = opa;
for(int i = 0; i < m; i++)
if(pai[i] != -1) ans[i] = 1^ans[pai[i]];
for(int i = 0; i < m; i++)
printf("%d", ans[i]);
puts("");
return 0;
}
}
r_a = r;
}
puts("impossible");
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 0; i < brabos.size(); i++)
| ~~^~~~~~~~~~~~~~~
alternating.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0; i < brabos.size(); i++) {
| ~~^~~~~~~~~~~~~~~
alternating.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(i == brabos.size()) i = 0;
| ~~^~~~~~~~~~~~~~~~
alternating.cpp:85:19: warning: unused variable 'cnt' [-Wunused-variable]
85 | static int cnt = 0;
| ^~~
alternating.cpp:22:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:24:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | scanf("%d %d", &wr[i].l, &wr[i].r); wr[i].id = i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp: At global scope:
alternating.cpp:85:19: warning: 'cnt' defined but not used [-Wunused-variable]
85 | static int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
3504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1740 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 4 |
Correct |
15 ms |
3180 KB |
Output is correct |
| 5 |
Correct |
39 ms |
4932 KB |
Output is correct |
| 6 |
Correct |
23 ms |
3016 KB |
Output is correct |
| 7 |
Correct |
41 ms |
4588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1872 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1744 KB |
Output is correct |
| 10 |
Correct |
39 ms |
5296 KB |
Output is correct |
| 11 |
Correct |
30 ms |
4292 KB |
Output is correct |
| 12 |
Correct |
33 ms |
4356 KB |
Output is correct |
| 13 |
Correct |
1 ms |
976 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 15 |
Correct |
44 ms |
4576 KB |
Output is correct |
| 16 |
Correct |
9 ms |
2228 KB |
Output is correct |
| 17 |
Correct |
36 ms |
4664 KB |
Output is correct |
| 18 |
Correct |
34 ms |
3712 KB |
Output is correct |
| 19 |
Correct |
2 ms |
720 KB |
Output is correct |
| 20 |
Correct |
40 ms |
4952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1076 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
