#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;
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]) 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]) 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:20: 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:19: 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:10: 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:15: warning: unused variable 'cnt' [-Wunused-variable]
85 | 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:85:15: warning: 'cnt' defined but not used [-Wunused-variable]
85 | static int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3156 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
972 KB |
no wires in direction 1 between segments 1 and 100000 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
no wires in direction 1 between segments 1 and 15 |
| 2 |
Halted |
0 ms |
0 KB |
- |
