#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], iscy[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), iscy[i]=1;
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 final)
int lst=0;
map<pii, bool> valid;
for (int i=1;i<=n;i++){
for (auto &u:f[i][0]) if (ind[u]){
if (!iscy[u] || 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;
}
if (im.size()==2){
pii srch = {*im.begin(), *next(im.begin())};
if (!valid.count(srch)) valid[srch] = 1;
if (all.empty()) valid[srch] = 0;
}
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);
}
}
int sz = bn.size();
pii want = {-1,-1};
for (auto &x:valid) if (x.second){
want = x.first;
break;
}
if (ruim && want.first==-1){ // pegar não-interseção
lst = bn.back();
for (int i=0;i<sz;i++){
int l = cb[bn[i]].first, r=cb[bn[i]].second;
if (l>cb[lst].second){
want = {lst, bn[i]};
// cerr << bn[i] << ' ' << lst << ' ' << " for " << cyd << '\n';
break;
}
if (l>r) break;
lst = bn[i];
}
}
// for (auto &x:bn) cerr << cb[x].first << ' ' << cb[x].second << '\n';
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<sz;i++) ty[bn[i]] = !ty[bn[i-1]];
}else{
for (int i=0;i<sz;i++){
if (bn[i]==want.first) want.first = m+i;
else if (bn[i]==want.second) want.second=m+i;
}
want.first-=m, want.second-=m;
if (want.second<want.first) swap(want.first, want.second);
bool color = 1;
if (want == ((pii){0,sz-1})){
for (int i=0;i<sz;i++){
ty[bn[i]] = color, color=!color;
}
}else{
for (int i=want.second;i<sz;i++){
ty[bn[i]] = color, color=!color;
}
for (int i=0;i<=want.first;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:69:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
69 | 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
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5092 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5116 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5092 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5116 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5092 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5116 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
13164 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4944 KB |
Output is correct |
| 3 |
Correct |
16 ms |
9224 KB |
Output is correct |
| 4 |
Correct |
26 ms |
11784 KB |
Output is correct |
| 5 |
Correct |
68 ms |
13316 KB |
Output is correct |
| 6 |
Correct |
42 ms |
11924 KB |
Output is correct |
| 7 |
Correct |
50 ms |
12840 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5456 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5200 KB |
Output is correct |
| 10 |
Correct |
56 ms |
13636 KB |
Output is correct |
| 11 |
Correct |
42 ms |
12672 KB |
Output is correct |
| 12 |
Correct |
40 ms |
13544 KB |
Output is correct |
| 13 |
Correct |
5 ms |
4944 KB |
Output is correct |
| 14 |
Correct |
4 ms |
4944 KB |
Output is correct |
| 15 |
Correct |
48 ms |
11596 KB |
Output is correct |
| 16 |
Correct |
24 ms |
12120 KB |
Output is correct |
| 17 |
Correct |
91 ms |
13564 KB |
Output is correct |
| 18 |
Correct |
79 ms |
11772 KB |
Output is correct |
| 19 |
Correct |
6 ms |
5712 KB |
Output is correct |
| 20 |
Correct |
40 ms |
11260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5092 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5116 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
