#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, m;
vector<int> adj[maxn];
struct seg{
int l, r, id;
seg(){}
seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){
if(r < l) r += n;
}
bool operator < (const seg& other) const{
if(l != other.l) return l < other.l;
return r > other.r;
}
} ee[maxn];
class comp{
public:
bool operator ()(seg a, seg b){
if(a.r != b.r) return a.r < b.r;
else return a.l < b.l;
}
};
struct segtree{
int st[maxn * 4], tag[maxn * 4];
void cast(int val, int v){
st[v] += val, tag[v] += val;
}
void push(int v){
if(tag[v]){
cast(tag[v], v * 2);
cast(tag[v], v * 2 + 1);
tag[v] = 0;
}
}
void upd(int l, int r, int val, int v, int L, int R){
if(l > R || r < L) return;
if(l <= L && r >= R){
st[v] += val, tag[v] += val;
return;
}
push(v);
int m = (L + R) / 2;
upd(l, r, val, v * 2, L, m);
upd(l, r, val, v * 2 + 1, m + 1, R);
st[v] = min(st[v * 2], st[v * 2 + 1]);
}
void upd(int l, int r, int val){ upd(l, r, val, 1, 0, n - 1);}
int qry(int l, int r, int v, int L, int R){
if(l > R || r < L) return INF;
if(l <= L && r >= R) return st[v];
push(v);
int m = (L + R) / 2;
return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
int qry(int l, int r){ return qry(l, r, 1, 0, n - 1);}
void insert(int l, int r, int val){
l %= n, r %= n;
if(l <= r) upd(l, r, val);
else upd(l, n - 1, val), upd(0, r, val);
}
} st[2];
signed main(void){
fastio;
cin>>n>>m;
vector<seg> e;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
a--, b--;
if(a == b + 1) a = 0, b = n - 1;
ee[i] = seg(a, b, i);
e.pb(seg(a, b, i));
if(a <= b) e.pb(seg(a + n, b + n, i));
}
vector<int> par(m, -1);
sort(e.begin(), e.end());
int tr = -1, tid = -1;
set<int> vis;
vector<seg> nw;
for(int i = 0; i < e.size(); i++){
auto [l, r, id] = e[i];
if(r <= tr) par[id] = tid;
else tr = r, tid = id;
}
for(int i = 0; i < m; i++){
if(par[i] == -1) nw.pb(ee[i]);
else{
while(par[par[i]] != -1) par[i] = par[par[i]];
adj[par[i]].pb(i);
}
}
sort(nw.begin(), nw.end());
vector<int> ans(m);
for(int i = 0; i < nw.size(); i++){
st[i % 2].insert(nw[i].l, nw[i].r, 1);
ans[nw[i].id] = i % 2;
for(auto id : adj[nw[i].id]){
st[(i % 2 == 0)].insert(ee[id].l, ee[id].r, 1);
ans[id] = (i % 2 == 0);
}
}
if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
for(auto x : ans) cout<<x;
cout<<"\n";
return 0;
}
if(nw.size() % 2 == 0){
cout<<"impossible\n";
return 0;
}
else{
for(int i = 0; i < nw.size(); i++){
st[i % 2].insert(nw[i].l, nw[i].r, -1);
st[(i % 2 == 0)].insert(nw[i].l, nw[i].r, 1);
ans[nw[i].id] ^= 1;
for(auto id : adj[nw[i].id]){
st[(i % 2 == 0)].insert(ee[id].l, ee[id].r, -1);
st[i % 2].insert(ee[id].l, ee[id].r, 1);
ans[id] ^= 1;
}
if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
for(auto x : ans) cout<<x;
cout<<"\n";
return 0;
}
}
cout<<"impossible\n";
}
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:95:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 0; i < e.size(); i++){
| ~~^~~~~~~~~~
alternating.cpp:109:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i = 0; i < nw.size(); i++){
| ~~^~~~~~~~~~~
alternating.cpp:127:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0; i < nw.size(); i++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3053 ms |
4956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3053 ms |
4956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3053 ms |
4956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3030 ms |
11976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3053 ms |
4956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
