#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 3e5+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];
if(pref[i] < 2) return puts("impossible"), 0;
}
sort(wr, wr+m);
bool virou = 0;
int fim = 0, aberto = -1;
vector<Wire> brabos;
memset(pai, -1, sizeof pai);
for(int i = 0; i < m; i++) {
auto [l, r, id] = wr[i];
if(make_pair(virou, fim) < make_pair(r < l || l < ini_mx, r)) {
brabos.push_back(wr[i]);
aberto = id;
fim = r;
virou |= r < l || l < ini_mx;
} else pai[id] = aberto;
}
/* puts("BRABOS: ");
printf("Size: %ld\n", brabos.size());
for(Wire x : brabos)
printf("(%d %d %d) ", x.l, x.r, x.id);
puts(""); */
vector<int> ans(m);
auto print = [&]() {
for(int i = 0; i < m; i++)
printf("%d", ans[i]);
puts("");
exit(0);
};
if(brabos[0].sz() == n) {
ans[brabos[0].id] = 1;
print();
}
if(brabos.size() % 2 == 0) {
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]];
print();
}
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]];
print();
}
}
r_a = r;
}
puts("impossible");
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < brabos.size(); i++)
| ~~^~~~~~~~~~~~~~~
alternating.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < brabos.size(); i++) {
| ~~^~~~~~~~~~~~~~~
alternating.cpp:106:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if(i == brabos.size()) i = 0;
| ~~^~~~~~~~~~~~~~~~
alternating.cpp:100:15: warning: unused variable 'cnt' [-Wunused-variable]
100 | static int cnt = 0;
| ^~~
alternating.cpp:22:7: 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:8: 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:100:15: warning: 'cnt' defined but not used [-Wunused-variable]
100 | static int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1356 KB |
no wires in direction 1 between segments 14 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1356 KB |
no wires in direction 1 between segments 14 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1356 KB |
no wires in direction 1 between segments 14 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3520 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1180 KB |
Output is correct |
| 4 |
Correct |
15 ms |
2704 KB |
Output is correct |
| 5 |
Correct |
43 ms |
3836 KB |
Output is correct |
| 6 |
Correct |
19 ms |
1748 KB |
Output is correct |
| 7 |
Correct |
33 ms |
3584 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1740 KB |
Output is correct |
| 10 |
Correct |
37 ms |
4124 KB |
Output is correct |
| 11 |
Correct |
27 ms |
3388 KB |
Output is correct |
| 12 |
Correct |
31 ms |
3276 KB |
Output is correct |
| 13 |
Correct |
1 ms |
588 KB |
Output is correct |
| 14 |
Correct |
1 ms |
588 KB |
Output is correct |
| 15 |
Correct |
35 ms |
3528 KB |
Output is correct |
| 16 |
Correct |
9 ms |
1276 KB |
Output is correct |
| 17 |
Correct |
34 ms |
3432 KB |
Output is correct |
| 18 |
Correct |
34 ms |
3148 KB |
Output is correct |
| 19 |
Correct |
2 ms |
716 KB |
Output is correct |
| 20 |
Correct |
48 ms |
3952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1356 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1356 KB |
no wires in direction 1 between segments 14 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
