#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int n, m, l[nx], r[nx], vs[nx], qs[nx], c[nx], vss[nx], f;
vector<int> add[nx], rem[nx], d[nx];
set<int> cur;
void dfs(int u)
{
vss[u]=1;
for (auto v:d[u])
{
if (vss[v]&&c[u]==c[v]) f=1;
if (!vss[v]) c[v]=!c[u], dfs(v);
}
}
struct segtree
{
int d[4*nx], lz[4*nx];
void pushlz(int l, int r, int i)
{
d[i]+=lz[i];
if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
lz[i]=0;
}
void update(int l, int r, int i, int ql, int qr, int vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr ,vl);
update(md+1, r, 2*i+1, ql, qr ,vl);
d[i]=min(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr)
{
pushlz(l, r, i);
if (qr<l||r<ql) return INT_MAX;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} s;
void addrange(int l, int r)
{
if (l<=r) s.update(1, n, 1, l, r, 1);
else s.update(1, n, 1, 1, r, 1), s.update(1, n, 1, l, n, 1);
}
int getmin(int l, int r)
{
if (l<=r) return s.query(1, n, 1, l, r);
else return min(s.query(1, n, 1, 1, r), s.query(1, n, 1, l, n));
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++)
{
cin>>l[i]>>r[i];
if (l[i]<=r[i]) add[l[i]].push_back(i), rem[r[i]].push_back(i);
else rem[r[i]].push_back(i), add[l[i]].push_back(i), cur.insert(i);
}
for (int i=1; i<=n; i++)
{
qs[i]+=qs[i-1];
for (auto x:add[i]) cur.insert(x);
if (cur.size()<2) return cout<<"impossible", 0;
if (cur.size()==2)
{
int u=*cur.begin(), v=*next(cur.begin());
d[u].push_back(v);
d[v].push_back(u);
vs[u]=vs[v]=1;
}
for (auto x:rem[i]) cur.erase(x);
}
for (int i=1; i<=m; i++) if (vs[i]&&!vss[i]) dfs(i);
if (f) return cout<<"impossible", 0;
for (int i=1; i<=m; i++) if (c[i]) addrange(l[i], r[i]);
for (int i=1; i<=m; i++)
{
if (!vs[i]) if (getmin(l[i], r[i])==0) addrange(l[i], r[i]), c[i]=1;
//cout<<i<<' '<<c[i]<<' '<<vs[i]<<'\n';
cout<<c[i];
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |