#include <bits/stdc++.h>
using namespace std;
/*
se p dois intervalos [a,b] a cobre b, ent a e b tem que ter tipos diferentes
resposta válida tem que ter alguem que cobre outro
ignorar os cobertos
pensar no círculo
vendo os independentes posso colocar eles de cores diferentes pra aproveitar interseções
parte com eles sozinhos tem que ter intervalos contidos bons
qnt par deles fechou
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 1e5+10;
vector<int> f[MAXN][2]; // {start, end} fios
pii cb[MAXN];
bool ty[MAXN];
bool ind[MAXN]; // se é independente, ciclo
int pai[MAXN]; // pros ruins, quem contem ele
int qnt[MAXN];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// cout << fixed << setprecision(7);
int n, m;
cin >> n >> m;
int a, b, cyd=0, cyl=1e9+1;
vector<pair<pii, int>> ord, cy;
for (int i=0;i<m;i++){
cin >> a >> b;
cb[i] = {a,b}, pai[i]=-1;
if(b<a){
if (b==a-1){
a=1,b=n;
cb[i]={a,b};
}else{
cyd = max(cyd, b), cyl = min(cyl, a);
cy.push_back({{a,-b}, i});
f[1][0].push_back(i);
f[b][1].push_back(i);
f[a][0].push_back(i);
continue;
}
}
ord.push_back({{a,-b}, i});
f[a][0].push_back(i);
f[b][1].push_back(i);
}
if (!ord.empty()) sort(ord.begin(), ord.end());
bool ruim = 0;
for (auto &x:ord){
x.first.second = -x.first.second;
if (x.first.second <= cyd) continue;
if (x.first.first >= cyl) break;
cyd = x.first.second, ind[x.second]=1, ruim^=1;
}
if (cy.empty() || !ord.empty() && ord[0].first.first == 1 && ord[0].first.second==n) ruim=0; // se tem um cara que cobre todo mundo ou nn tem ciclos
else{ // ver ciclos
sort(cy.begin(), cy.end());
cyd = 0;
for (auto &x:cy){
x.first.second*=-1;
if (x.first.second<=cyd) continue;
cyd=x.first.second, ind[x.second]=1, ruim^=1;
}
}
ord.clear();
cy.clear();
set<int> all, im;
vector<int> bn; // bons (ciclos aparecem só no inicio)
int lst;
for (int i=1;i<=n;i++){
for (auto &u:f[i][0]) if (ind[u]){
if (i<cyl) bn.push_back(u);
im.insert(u);
lst = u;
}
while (!f[i][0].empty()){
int u = f[i][0].back();
f[i][0].pop_back();
if (ind[u]) continue;
all.insert(u);
pai[u] = lst; // se um ruim cobre um trecho sem importantes ent ele deveria ser importante
}
if (im.size()+all.size()<2){
cout << "impossible\n";
return 0;
}
qnt[i]=all.size();
while (!f[i][1].empty()){
int u = f[i][1].back();
f[i][1].pop_back();
if (ind[u]) im.erase(u);
else all.erase(u);
}
}
// for (int i=0;i<m;i++){
// cerr << i;
// if (!ind[i]) cerr << " filho de " << pai[i];
// cerr << '\n';
// }
pii want = {-1,-1};
if (ruim && want.first==-1){ // quantidade é ímpar e não tem uma interseção que é válida nem um cara que cobre todo mundo
cout << "impossible\n";
return 0;
}
if (!ruim){
ty[bn[0]]=1;
for (int i=1;i<bn.size();i++) ty[bn[i]] = !ty[bn[i-1]];
}else{
int st = -1;
for (int i=0;i<bn.size();i++) if (i==want.first || i==want.second){
st=i;
break;
}
bool color = 1;
for (int i=st;i<bn.size();i++) ty[bn[i]]=color, color=!color;
for (int i=0;i<st;i++) ty[bn[i]]=color, color=!color;
}
for (int i=0;i<m;i++){
if (pai[i] == -1) cout << ty[i];
else cout << !ty[pai[i]];
}
cout << '\n';
return 0;
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:70:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
70 | if (cy.empty() || !ord.empty() && ord[0].first.first == 1 && ord[0].first.second==n) ruim=0; // se tem um cara que cobre todo mundo ou nn tem ciclos
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i=1;i<bn.size();i++) ty[bn[i]] = !ty[bn[i-1]];
| ~^~~~~~~~~~
alternating.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int i=0;i<bn.size();i++) if (i==want.first || i==want.second){
| ~^~~~~~~~~~
alternating.cpp:141:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i=st;i<bn.size();i++) ty[bn[i]]=color, color=!color;
| ~^~~~~~~~~~
alternating.cpp:99:20: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | pai[u] = lst; // se um ruim cobre um trecho sem importantes ent ele deveria ser importante
| ~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6900 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6900 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6900 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
14336 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6736 KB |
Output is correct |
| 3 |
Correct |
13 ms |
10760 KB |
Output is correct |
| 4 |
Correct |
24 ms |
13488 KB |
Output is correct |
| 5 |
Correct |
45 ms |
13820 KB |
Output is correct |
| 6 |
Correct |
38 ms |
12796 KB |
Output is correct |
| 7 |
Correct |
45 ms |
13564 KB |
Output is correct |
| 8 |
Correct |
3 ms |
7164 KB |
Output is correct |
| 9 |
Correct |
3 ms |
6992 KB |
Output is correct |
| 10 |
Correct |
47 ms |
14404 KB |
Output is correct |
| 11 |
Correct |
32 ms |
12804 KB |
Output is correct |
| 12 |
Correct |
40 ms |
14596 KB |
Output is correct |
| 13 |
Correct |
2 ms |
6992 KB |
Output is correct |
| 14 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 15 |
Correct |
42 ms |
12284 KB |
Output is correct |
| 16 |
Correct |
24 ms |
13580 KB |
Output is correct |
| 17 |
Correct |
88 ms |
15216 KB |
Output is correct |
| 18 |
Correct |
75 ms |
12572 KB |
Output is correct |
| 19 |
Correct |
4 ms |
6992 KB |
Output is correct |
| 20 |
Correct |
44 ms |
12796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6900 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
