#include <iostream>
#include <vector>
using namespace std;
#define ff first
#define ss second
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> seg(m);
bool case_a_b = 1;
vector<vector<pair<int, int>>> konce(n + 1);
for (int i = 0; i < m; i++) {
cin >> seg[i].ff >> seg[i].ss;
if (seg[i].ff > seg[i].ss) case_a_b = 0;
konce[seg[i].ff].push_back({seg[i].ss, i});
}
if (case_a_b) {
int akt_0 = 0;
int akt_1 = 0;
vector<int> odp(m, 0);
for (int i = 1; i <= n; i++) {
sort(konce[i].begin(), konce[i].end());
if (akt_0 + 1 < i || akt_1 + 1 < i) {
cout << "impossible\n";
return 0;
}
if (akt_0 < akt_1) {
if (konce[i].size() > 0) {
akt_0 = max(akt_0, konce[i].back().first);
konce[i].pop_back();
}
if (konce[i].size() > 0) {
akt_1 = max(akt_1, konce[i].back().first);
odp[konce[i].back().second] = 1;
konce[i].pop_back();
}
}
else {
if (konce[i].size() > 0) {
akt_1 = max(akt_1, konce[i].back().first);
odp[konce[i].back().second] = 1;
konce[i].pop_back();
}
if (konce[i].size() > 0) {
akt_0 = max(akt_0, konce[i].back().first);
konce[i].pop_back();
}
}
}
if (akt_0 < n || akt_1 < n) {
cout << "impossible\n";
return 0;
}
for (int i = 0; i < m; i++) cout << odp[i];
return 0;
}
int K = 1 << m;
for (int msk = 0; msk < K; msk++) {
vector<vector<int>> tab(n + 1, vector<int>(2, 0));
for (int i = 0; i < m; i++) {
int bit = 0;
if ((1 << i) & msk) bit = 1;
int a = seg[i].ff, b = seg[i].ss;
if (b < a) {
for (int i = a; i <= n; i++) tab[i][bit] = 1;
for (int i = 1; i <= b; i++) tab[i][bit] = 1;
}
else for (int i = a; i <= b; i++) tab[i][bit] = 1;
}
bool git = 1;
for (int i = 1; i <= n; i++) {
if (!tab[i][0] || !tab[i][1]) git = 0;
}
if (git) {
for (int i = 0; i < m; i++) {
int bit = 0;
if ((1 << i) & msk) bit = 1;
cout << bit;
}
return 0;
}
}
cout << "impossible\n";
return 0;
}
# | 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... |