#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m;
cin >> n >> m;
bool noround = true;
vector<pair<int, int>> v;
int a, b;
rep(i, 0, m) {
cin >> a >> b;
if(a > b) noround = false;
v.pb({a, b});
}
if(noround) {
vector<pair<pair<int, int>, int>> v2;
rep(i, 0, m) v2.pb({v[i], i});
ranges::sort(v2);
a = 0, b = 0;
vector<bool> ans(m);
repIn2(lr, i, v2) {
auto [l, r] = lr;
if(a < b) {
if(l - 1 > a) { cout << "impossible\n"; return 0; }
a = r;
}
else {
if(l - 1 > b) { cout << "impossible\n"; return 0; }
b = r;
ans[i] = 1;
}
}
if(a < n || b < n) { cout << "impossible\n"; return 0; }
rep(i, 0, m) cout << ans[i];
cout << '\n';
return 0;
}
rep(mask, 0, 1 << m) {
vector<bool> a(n), b(n);
rep(i, 0, m) {
rep(j, v[i].first, v[i].second) {
(mask & (1 << i) ? a : b)[j - 1] = true;
if(j == n) j -= n;
}
(mask & (1 << i) ? a : b)[v[i].second - 1] = true;
}
bool g = true;
rep(i, 0, n) g = g && a[i] && b[i];
if(g) {
rep(i, 0, m) cout << ((mask >> i) & 1);
cout << '\n';
return 0;
}
}
cout << "impossible\n";
}
# | 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... |