#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
void open_file(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 1e5 + 25;
int par[maxN];
vector<int> g[maxN];
void make_set() {
for (int i = 0; i <= maxN; i++) par[i] = i;
}
int find_set(int v) {
if (v == par[v])
return v;
return par[v] = find_set(par[v]);
}
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x != y) par[y] = x;
}
struct segtree {
int t[4 * maxN], lazy[4 * maxN], n;
void init(int _n) {
n = _n;
for (int i = 0; i < 4 * maxN; i++)
t[i] = lazy[i] = 0;
}
void prop(int v, int tl, int tr) {
if (!lazy[v]) return;
t[v] += lazy[v];
if (tl != tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
} lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int val) {
prop(v, tl, tr);
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
lazy[v] += val;
prop(v, tl, tr);
return;
} int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r, val);
update(2 * v + 1, tm + 1, tr, l, r, val);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
int query(int v, int tl, int tr, int l, int r) {
prop(v, tl, tr);
if (l > r) return -inf;
if (tl == l && tr == r)
return t[v];
int tm = (tl + tr) / 2;
return min(query(2 * v, tl, tm, l, min(r, tm)),
query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
void update(int l, int r, int val) {
if (r > n) r -= n;
if (l <= r) {
update(1, 1, n, l, r, val);
}
else {
update(1, 1, n, l, n, val);
update(1, 1, n, 1, r, val);
}
}
int eval() {
return query(1, 1, n, 1, n);
}
} seg[2];
bool check() {
return (seg[0].eval() > 0 && seg[1].eval() > 0);
}
struct line {
int x, y, id, cl, clr;
line() {
}
line(int _x, int _y, int _id) {
x = _x; y = _y; id = _id; cl = clr = -1;
}
bool operator<(const line &p) {
return make_pair(x, -y) < make_pair(p.x, -p.y);
}
} arr[maxN];
bool comp(line a, line b) {
return a.id < b.id;
}
vector<line> good;
int n, m, mx, mxi, cld[maxN];
void elim() {
deque<line> dq;
sort(arr + 1, arr + m + 1);
for (int i = 1; i <= n; i++) {
if (dq.empty() || dq.back().y < arr[i].y) dq.push_back(arr[i]);
else cld[arr[i].id] = dq.back().id;
} while (dq.size() && dq.front().y <= mx) {
cld[dq.front().id] = mxi; dq.pop_front();
} for (line x : dq) good.pb(x);
for (int i = 1; i <= m; i++)
if (cld[arr[i].id]) arr[i].cl = cld[arr[i].id];
make_set();
for (int i = 1; i <= m; i++)
if (arr[i].cl != -1) union_set(arr[i].cl, arr[i].id);
for (int i = 1; i <= m; i++) {
if (arr[i].cl != -1) {
arr[i].cl = find_set(arr[i].id);
g[arr[i].cl].pb(arr[i].id);
} else g[arr[i].id].pb(arr[i].id);
}
}
void even() {
for (int i = 0; i < good.size(); i++)
arr[good[i].id].clr = i % 2;
for (int i = 1; i <= m; i++)
if (arr[i].clr == -1) arr[i].clr = (arr[arr[i].cl].clr ^ 1);
for (int i = 1; i <= m; i++) {
seg[arr[i].clr].update(arr[i].x, arr[i].y, 1);
}
if (check()) {
for (int i = 1; i <= m; i++)
cout << arr[i].clr;
} else {
cout << "impossible";
} exit(0);
}
void odd() {
for (int i = 0; i < good.size(); i++)
arr[good[i].id].clr = i % 2;
for (int i = 1; i <= m; i++)
if (arr[i].clr == -1) arr[i].clr = (arr[arr[i].cl].clr ^ 1);
for (int i = 1; i <= m; i++)
seg[arr[i].clr].update(arr[i].x, arr[i].y, 1);
if (check()) {
for (int i = 1; i <= m; i++)
cout << arr[i].clr;
exit(0);
} for (int i = 0; i < good.size(); i++) {
for (int j : g[good[i].id]) {
seg[arr[j].clr].update(arr[j].x, arr[j].y, -1);
arr[j].clr ^= 1;
seg[arr[j].clr].update(arr[j].x, arr[j].y, 1);
} if (check()) {
for (int j = 1; j <= m; j++)
cout << arr[j].clr;
exit(0);
}
} cout << "impossible";
exit(0);
}
void solve() {
cin >> n >> m;
seg[0].init(n); seg[1].init(n);
for (int i = 1; i <= m; i++) {
int l, r; cin >> l >> r;
if (l > r) {
if (mx < r) {
mx = r; mxi = i;
} r += n;
} arr[i] = {l, r, i};
} elim();
sort(arr + 1, arr + m + 1, comp);
sort(all(good), comp);
if (good.size() % 2 == 0) even();
else odd();
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << '\n';
}
return 0;
}
Compilation message
alternating.cpp: In function 'void even()':
alternating.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int i = 0; i < good.size(); i++)
| ~~^~~~~~~~~~~~~
alternating.cpp: In function 'void odd()':
alternating.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for (int i = 0; i < good.size(); i++)
| ~~^~~~~~~~~~~~~
alternating.cpp:177:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | } for (int i = 0; i < good.size(); i++) {
| ~~^~~~~~~~~~~~~
alternating.cpp: In function 'void open_file(std::string)':
alternating.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp: In function 'void make_set()':
alternating.cpp:40:44: warning: iteration 100025 invokes undefined behavior [-Waggressive-loop-optimizations]
40 | for (int i = 0; i <= maxN; i++) par[i] = i;
| ~~~~~~~^~~
alternating.cpp:40:23: note: within this loop
40 | for (int i = 0; i <= maxN; i++) par[i] = i;
| ~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
11528 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
11528 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
11528 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
12252 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
42 ms |
12132 KB |
Output is correct |
| 4 |
Correct |
23 ms |
12120 KB |
Output is correct |
| 5 |
Incorrect |
56 ms |
14548 KB |
'impossible' claimed, but there is a solution |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
1 ms |
11612 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
11528 KB |
'impossible' claimed, but there is a solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
