QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380917 | #2434. Single Cut of Failure | ckiseki# | WA | 265ms | 31780kb | C++20 | 4.1kb | 2024-04-07 14:58:46 | 2024-04-07 14:58:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
struct M {
int mx;
int pos;
};
M operator+(M a, M b) {
return a.mx < b.mx ? b : a;
}
struct Segtree {
int n;
vector<M> st;
vector<int> lz;
Segtree(int n_) : n(n_), st(n * 2), lz(n) {
for (int i = 0; i < n; i++)
st[i + n] = {0, i};
for (int i = n - 1; i > 0; i--)
st[i] = st[i << 1] + st[i << 1 | 1];
}
void upd(int p, int v) {
st[p].mx += v;
if (p < n) lz[p] += v;
}
void pull(int p) {
while (p >>= 1) {
st[p] = st[p << 1] + st[p << 1 | 1];
st[p].mx += lz[p];
}
}
void add(int l, int r, int v) {
if (l >= r) return;
assert(l < n && r <= n);
int tl = l, tr = r;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) upd(l++, v);
if (r & 1) upd(--r, v);
}
pull(tl + n), pull(tr - 1 + n);
}
M query() {
return st[1];
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cout.precision(20);
cout << fixed;
int n, w, h;
cin >> n >> w >> h;
auto mapping = [&](int x, int y) {
if (y == 0) {
return x;
} else if (x == w) {
return w + y;
} else if (y == h) {
return w + h + (w - x);
} else {
return w + h + w + (h - y);
}
};
const int C = w + h + w + h;
vector<int> u;
vector<tuple<int,int,int,int>> evt;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int l = mapping(x1, y1);
int r = mapping(x2, y2);
u.push_back(l);
u.push_back(r);
if (l > r)
swap(l, r);
assert(l < r);
// rng[i] = {l, r};
evt.emplace_back(0, 1, l, r);
evt.emplace_back(l, -2, l, r);
evt.emplace_back(r, 2, l, r);
evt.emplace_back(C, -1, l, r);
}
evt.emplace_back(mapping(0, 0), 0, 0, 0);
evt.emplace_back(mapping(w, 0), 0, 0, 0);
evt.emplace_back(mapping(w, h), 0, 0, 0);
evt.emplace_back(mapping(0, h), 0, 0, 0);
ranges::sort(evt);
u.push_back(mapping(0, 0));
u.push_back(mapping(w, 0));
u.push_back(mapping(w, h));
u.push_back(mapping(0, h));
ranges::sort(u);
Segtree sgt(u.size());
int global = 0;
for (size_t i = 0, j; i < evt.size(); i = j) {
for (j = i; j < evt.size(); j++) {
if (get<0>(evt[j]) != get<0>(evt[i])) break;
auto [_, tp, l, r] = evt[j];
if (tp != 0) {
l = lower_bound(all(u), l) - u.begin();
r = lower_bound(all(u), r) - u.begin();
debug(l, r);
sgt.add(l, r, tp);
}
if (abs(tp) == 2) {
if (tp < 0) {
global += 1;
} else {
global -= 1;
}
}
}
auto R = sgt.query();
R.mx += global;
auto unmapping = [&](long double z) -> pair<long double, long double> {
if (z <= w) {
return {z, 0};
} else if (z <= w + h) {
return {w, z - w};
} else if (z <= w + h + w) {
return {w - (z - w - h), h};
} else {
return {0, h - (z - w - h - w)};
}
};
assert(R.mx >= 0 && R.mx <= n);
if (R.mx == n) {
long double a = (get<0>(evt[i]) + get<0>(evt[j])) / 2.0;
long double b = (u[R.pos] + u[(R.pos + 1) % u.size()]) / 2.0;
auto [ax, ay] = unmapping(a);
auto [bx, by] = unmapping(b);
cout << 1 << '\n';
cout << ax << ' ' << ay << ' ' << bx << ' ' << by << '\n';
return 0;
}
}
cout << 2 << '\n';
cout << 0.5 << ' ' << 0 << ' ' << w - 0.5 << ' ' << h << '\n';
cout << 0.5 << ' ' << h << ' ' << w - 0.5 << ' ' << 0 << '\n';
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 3924kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3736kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3928kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3808kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3744kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 4032kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 4028kb
Test #9:
score: 0
Accepted
time: 265ms
memory: 31780kb
Test #10:
score: -100
Wrong Answer
time: 265ms
memory: 30596kb