#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
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);
}
sort(ord.begin(), ord.end());
bool ruim = 0;
for (auto &x:ord){
x.first.second *= -1;
if (x.first.second <= cyd) continue;
if (x.first.first >= cyl) break;
cyd = x.first.second, ind[x.second]=1, ruim^=1;
}
if (ord[0].first.first == 1 && ord[0].first.second==n) ruim=0; // se tem um cara que cobre todo mundo
else if (!cy.empty()){ // ver ciclos
sort(cy.begin(), cy.end());
cyd = (-cy[0].first.second) - 1;
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;
map<pii, bool> vld; // se é válida a interseção entre a,b
vector<int> bn; // bons (ciclos aparecem só no inicio)
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);
}
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] = *im.begin(); // se um ruim cobre um trecho sem importantes ent ele deveria ser importante
}
if (im.size()+all.size()<2){
cout << "impossible\n";
return 0;
}
if (im.size()==2){
pii srch = {*im.begin(), *next(im.begin())};
if (!vld.count(srch)) vld[srch] = 1;
vld[srch] = vld[srch]&(!all.empty());
}
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);
}
}
pii want = {-1,-1};
for (auto &x:vld) if (x.second) want = x.first;
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:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int i=1;i<bn.size();i++) ty[bn[i]] = !ty[bn[i-1]];
| ~^~~~~~~~~~
alternating.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i=0;i<bn.size();i++) if (i==want.first || i==want.second){
| ~^~~~~~~~~~
alternating.cpp:136:24: 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=st;i<bn.size();i++) ty[bn[i]]=color, color=!color;
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6480 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6224 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6224 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6480 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6224 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6224 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6480 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6224 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6224 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
13872 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6224 KB |
Output is correct |
| 3 |
Correct |
16 ms |
10504 KB |
Output is correct |
| 4 |
Correct |
27 ms |
13164 KB |
Output is correct |
| 5 |
Correct |
53 ms |
14588 KB |
Output is correct |
| 6 |
Correct |
43 ms |
13052 KB |
Output is correct |
| 7 |
Incorrect |
43 ms |
13828 KB |
no wires in direction 1 between segments 33 and 35 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6480 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6224 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6224 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
