# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
121031 | IOrtroiii | Alternating Current (BOI18_alternating) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int color[N];
int main() {
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<tuple<int, int, int>> vals;
for (int i = 1; i <= m; ++i) {
int l, r;
cin >> l >> r;
assert(l <= r);
vals.emplace_back(l, -r, i);
}
sort(vals.begin(), vals.end());
int gol = 0;
int gor = 0;
for (auto v : vals) {
int l, r, id;
tie(l, r, id) = v;
r = -r;
if (gol < gor) {
if (l > gol + 1) {
puts("impossible");
return 0;
}
color[id] = 0;
gol = max(gol, r);
} else {
if (l > gor + 1) {
puts("impossible");
return 0;
}
color[id] = 1;
gor = max(gor, r);
}
}
if (min(gol, gor)) < n) {
puts("impossible");
return 0;
}
for (int i = 1; i <= m; ++i) {
printf("%d", color[i]);
}
}