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;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
pii special[mn];
int state[mn];
bool getCur (int mask, int pos) {
return mask >> pos & 1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<int> orda, ordb, pickSpec;
vector<tpl> regular;
/// read wires info
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
if (a <= b) regular.emplace_back(a, b, i);
else {
special[i] = {a, b};
orda.push_back(i);
ordb.push_back(i);
}
}
sort(all(orda), [&] (int a, int b) { return special[a].first < special[b].first; });
sort(all(ordb), [&] (int a, int b) { return special[a].second > special[b].second; });
/// only pick candidates that has the chance to contribute to the answer
for (int i = 0; i < 4 && i < orda.size(); i++) pickSpec.push_back(orda[i]);
for (int i = 0; i < 4 && i < ordb.size(); i++) pickSpec.push_back(ordb[i]);
sort(all(pickSpec)), filter(pickSpec);
/// sort regular segments
sort(all(regular), [&] (tpl a, tpl b) {
int a0, a1, a2, b0, b1, b2; tie(a0, a1, a2) = a, tie(b0, b1, b2) = b;
if (a1 == b1) return (a0 == b0 ? a2 < b2 : a0 < b0);
return a1 < b1;
});
// for (auto [a, b, c] : regular) {
// cout << a << " " << b << " " << c << endl;
// }
/// find valid answer
for (int mask = 0; mask < (1 << pickSpec.size()); mask++) {
// calculate contribute of special segments
int si = 0, sj = 0, ti = n + 1, tj = n + 1;
for (int i = 0; i < pickSpec.size(); i++) {
int a, b; tie(a, b) = special[pickSpec[i]];
// cout << "spec " << pickSpec[i] << " " << a << " " << b << "\n";
if (getCur(mask, i)) {
state[pickSpec[i]] = 1;
si = max(si, b), ti = min(ti, a);
}
else {
state[pickSpec[i]] = 0;
sj = max(sj, b), tj = min(tj, a);
}
}
// cout << "try " << si << " " << sj << " -> " << ti << " " << tj << "\n";
// calculate contribute of regular segments
for (tpl item : regular) {
int a, b, idx; tie(a, b, idx) = item;
if (a <= min(si, sj) + 1 && si < ti - 1 && sj < tj - 1) {
if (si < sj) si = max(si, b), state[idx] = 1;
else sj = max(sj, b), state[idx] = 0;
}
else if (a <= si + 1 && si < ti - 1) si = max(si, b), state[idx] = 1;
else if (a <= sj + 1 && sj < tj - 1) sj = max(sj, b), state[idx] = 0;
}
// check answers
if (si >= ti - 1 && sj >= tj - 1) {
for (int i = 0; i < m; i++) cout << state[i];
return 0;
}
}
cout << "impossible";
return 0;
}
Compilation message (stderr)
alternating.cpp: In function 'int main()':
alternating.cpp:44:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < 4 && i < orda.size(); i++) pickSpec.push_back(orda[i]);
| ~~^~~~~~~~~~~~~
alternating.cpp:45:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < 4 && i < ordb.size(); i++) pickSpec.push_back(ordb[i]);
| ~~^~~~~~~~~~~~~
alternating.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < pickSpec.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
# | 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... |