#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define Pii pair<pair<int, int>, int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int n, from[N], last2[N], last3[N];
set<Pii> S;
struct seg{
int a, b, id;
} p[N];
int try_(seg s) {
queue<int> q;
q.push(s.id);
from[s.id] = 0;
while(q.size()) {
int u = q.front();
q.pop();
if(p[u].b == n) return s.id;
if(p[u].b > n && (s.a > p[u].b || last3[p[u].b] < s.a) && last2[p[u].b] == 0) return s.id;
if (p[u].b >= n) continue;
while (S.upper_bound({{p[u].b + 1, 0}, 0}) != S.begin()) {
Pii x = *--S.upper_bound({{p[u].b + 1, 0}, 0});
if (last2[p[u].b] < x.f.f) q.push(x.s), from[x.s] = u, S.erase(x);
else break;
}
}
return -1;
}
bool cmp(seg a, seg b) {
return (a.a < b.a);
}
int len(int a, int b) {
return (b >= a ? b - a + 1 : n - a + 1 + b);
}
int get(int x, int a) {
if(x >= a) return x - a + 1;
return n - a + 1 + x;
}
signed main() {
int m;
cin >> n >> m;
int mx = 0;
for(int i = 1; i <= m; i++) {
cin >> p[i].a >> p[i].b;
p[i].id = i;
if(len(p[i].a, p[i].b) > len(p[mx].a, p[mx].b)) mx = i;
}
int st = p[mx].a;
vector<int> c(n + 5);
for(int i = 1; i <= m; i++) {
p[i].a = get(p[i].a, st);
p[i].b = get(p[i].b, st);
++c[p[i].a], --c[p[i].b + 1];
if(p[i].a > p[i].b) ++c[1];
// cout << p[i].a << " " << p[i].b << "\n";
}
for(int i = 1; i <= n; i++) {
c[i] += c[i - 1];
last3[i] = last3[i - 1];
last2[i] = last2[i - 1];
if(c[i] == 1) {
cout << "impossible";
return 0;
}
if(c[i] == 2) last2[i] = i;
if(c[i] <= 3) last3[i] = i;
}
vector<seg> x;
for(int i = 1; i <= m; i++) {
if(p[i].a <= p[mx].b + 1) x.push_back(p[i]);
else S.insert({{p[i].a, (p[i].a < p[i].b ? p[i].b : p[i].b + n)}, i});
}
sort(x.begin(), x.end(), cmp);
int ST = 0;
while(x.size()) {
seg s = x.back(); x.pop_back();
ST = try_(s);
if(ST != -1) break;
}
if(ST == -1) {
cout << "impossible";
return 0;
}
vector<int> d(m + 5);
for(int i = 1; i <= m; i++) d[i] = -1;
S.clear();
for(int i = 1; i <= m; i++) {
if(p[i].a <= p[mx].b + 1) {}
else S.insert({{p[i].a, (p[i].a < p[i].b ? p[i].b : p[i].b + n)}, i});
}
vector<int> ans(m + 5); ans[mx] = 1;
int EN = try_(p[ST]);
while(EN) {
ans[EN] = 1;
EN = from[EN];
}
for(int i = 1; i <= m; i++) cout << ans[i] << "";
}
/*
10 5
1 5
6 7
5 1
7 2
2 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
no wires in direction 0 between segments 1 and 15 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
no wires in direction 0 between segments 1 and 15 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
no wires in direction 0 between segments 1 and 15 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
5592 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1468 KB |
no wires in direction 0 between segments 1 and 100000 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
no wires in direction 0 between segments 1 and 15 |
| 3 |
Halted |
0 ms |
0 KB |
- |
