QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216804 | #2434. Single Cut of Failure | Swarthmore# | WA | 850ms | 81976kb | C++14 | 6.8kb | 2023-10-16 01:05:33 | 2023-10-16 01:05:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point{
ll x,y;
Point (ll x_ = 0,ll y_ = 0) : x(x_), y(y_) {}
};
struct Seg{
Point u,v;
};
struct Invl{
ll l,r;
};
const int maxn = 1000005;
const ll inf = 1234567890;
Seg s[maxn],s2[maxn];
Point rotate90(Point p, ll h){
return Point(h-p.y,p.x);
}
Point rotate90_inv(Point p, ll h){ // original h
return Point(p.y,h-p.x);
}
inline int onSide(Point p,int w,int h){
if (p.y == 0) return 0;
if (p.x == w) return 1;
if (p.y == h) return 2;
if (p.x == 0) return 3;
assert(false);
}
Point inversions(ll x_lower, ll x_upper, ll y_lower, ll y_upper, vector<Invl> inv){
int n = inv.size();
assert(x_lower < x_upper);
assert(y_lower < y_upper);
if (n == 0){
return {x_lower + 1, y_lower + 1};
}
sort(inv.begin(), inv.end(), [](const Invl & a,const Invl & b){
return a.l < b.l;
});
vector<ll> pre_min(n+1), suf_max(n+1);
pre_min[0] = inf;
for (int i = 1;i <= n;i++){
pre_min[i] = min(pre_min[i-1], inv[i-1].r);
}
suf_max[n] = -inf;
for (int i = n;i >= 1;i--){
suf_max[i-1] = max(suf_max[i], inv[i-1].r);
}
inv.push_back({inf, inf});
for (int i = 0;i <= n;i++){
ll x_range_lower;
if (i != 0) x_range_lower = max(x_lower+1, inv[i-1].l+1);
else x_range_lower = x_lower + 1;
ll x_range_upper = min(x_upper-1, inv[i].l-1);
if (x_range_lower > x_range_lower) continue;
// Consider x in this range;
ll y_range_lower = max(suf_max[i] + 1, y_lower + 1);
ll y_range_upper = min(pre_min[i] - 1, y_upper - 1);
if (y_range_lower <= y_range_upper){
return {x_range_lower, y_range_lower};
}
}
return {-1,-1};
};
ostream& operator<<(ostream & os, Point p){
os << (p.x / 2);
if (p.x % 2 == 1) os << ".5";
os << " ";
os << (p.y / 2);
if (p.y % 2 == 1) os << ".5";
return os;
}
int main(){
int n;
cin >> n;
ll w,h;
cin >> w >> h;
w <<= 1;
h <<= 1;
for (int i = 1;i <= n;i++){
cin >> s[i].u.x >> s[i].u.y >> s[i].v.x >> s[i].v.y;
s[i].u.x <<= 1;
s[i].u.y <<= 1;
s[i].v.x <<= 1;
s[i].v.y <<= 1;
}
// Check "horizontal 1 way"
for (int i = 1;i <= n;i++){
s2[i] = s[i];
}
for (int i = 0;i < 2;i++){
ll x_upper = w;
ll x_lower = 0;
ll y_upper = w;
ll y_lower = 0;
vector<Invl> inv;
for (int j = 1;j <= n;j++){
Point u = s2[j].u;
Point v = s2[j].v;
int u_side = onSide(u, w, h);
int v_side = onSide(v, w, h);
if (u_side % 2 == 1 && v_side % 2 == 1) continue;
if (u_side % 2 == 0 && v_side % 2 == 0){
if (u_side < v_side) swap(u,v);
inv.push_back((Invl){u.x, v.x});
}
else{
if (u_side % 2 == 0){
swap(u,v);
swap(u_side,v_side);
}
if (u_side == 1 && v_side == 0){
y_lower = max(y_lower, v.x);
}
if (u_side == 1 && v_side == 2){
x_lower = max(x_lower, v.x);
}
if (u_side == 3 && v_side == 0){
y_upper = min(y_upper, v.x);
}
if (u_side == 3 && v_side == 2){
x_upper = min(x_upper, v.x);
}
}
}
// printf("x in [%lld, %lld] y in [%lld,%lld]\n",x_lower,x_upper,y_lower,y_upper);
if (x_lower < x_upper && y_lower < y_upper){
// Find restriction on lower - upper edges
auto [lower,upper] = inversions(x_lower, x_upper, y_lower, y_upper, inv);
if (lower > 0){
cout << "1\n";
Point x = Point(lower, h);
Point y = Point(upper, 0);
if (i == 1){
x = rotate90_inv(x, w);
y = rotate90_inv(y, w);
}
cout << x << " " << y << endl;
exit(0);
}
}
for (int j = 1;j <= n;j++){
s2[j].u = rotate90(s2[j].u, h);
s2[j].v = rotate90(s2[j].v, h);
}
swap(w,h);
}
for (int i = 1;i <= n;i++){
s2[i] = s[i];
}
for (int i = 0;i < 4;i++){
ll x_lower = 0;
ll x_upper = w;
ll y_lower = 0;
ll y_upper = h;
vector<Invl> inv;
bool tf = true;
for (int j = 1;j <= n;j++){
Point u = s2[j].u;
Point v = s2[j].v;
int u_side = onSide(u, w, h);
int v_side = onSide(v, w, h);
if (u_side % 2 != v_side % 2){
if (u_side % 2 == 0){
swap(u,v);
swap(u_side, v_side);
}
if (u_side == 1 && v_side == 2){
tf = false;
break;
}
if (u_side == 1 && v_side == 0){
x_lower = max(x_lower, v.x);
}
if (u_side == 3 && v_side == 0){
inv.push_back({v.x, u.y});
}
if (u_side == 3 && v_side == 2){
y_upper = min(y_upper, u.y);
}
}
else if (u_side % 2 == 0){
if (u_side != 0){
swap(u,v);
swap(u_side, v_side);
}
x_lower = max(x_lower, u.x);
}
else{
if (u_side != 3){
swap(u,v);
swap(u_side, v_side);
}
y_lower = max(y_lower, u.y);
}
}
if (tf && x_lower < x_upper && y_lower < y_upper){
// Find restriction on lower - upper edges
auto [lower,upper] = inversions(x_lower, x_upper, y_lower, y_upper, inv);
if (lower > 0){
cout << "1\n";
Point x = Point(lower, 0);
Point y = Point(0, upper);
for (int j = 1;j <= i;j++){
x = rotate90_inv(x, w);
y = rotate90_inv(y, w);
swap(h,w);
}
cout << x << " " << y << endl;
exit(0);
}
}
for (int j = 1;j <= n;j++){
s2[j].u = rotate90(s2[j].u, h);
s2[j].v = rotate90(s2[j].v, h);
}
swap(w,h);
}
cout << 2 << endl;
cout << Point(1, 0) << " " << Point(w-1,h) << endl;
cout << Point(w-1, 0) << " " << Point(1,h) << endl;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 66256kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 66132kb
Test #3:
score: 0
Accepted
time: 4ms
memory: 66036kb
Test #4:
score: 0
Accepted
time: 4ms
memory: 65984kb
Test #5:
score: 0
Accepted
time: 3ms
memory: 66336kb
Test #6:
score: 0
Accepted
time: 6ms
memory: 66296kb
Test #7:
score: 0
Accepted
time: 3ms
memory: 66096kb
Test #8:
score: 0
Accepted
time: 4ms
memory: 66040kb
Test #9:
score: 0
Accepted
time: 132ms
memory: 66104kb
Test #10:
score: 0
Accepted
time: 147ms
memory: 81976kb
Test #11:
score: 0
Accepted
time: 204ms
memory: 73776kb
Test #12:
score: 0
Accepted
time: 211ms
memory: 66332kb
Test #13:
score: 0
Accepted
time: 204ms
memory: 66324kb
Test #14:
score: 0
Accepted
time: 215ms
memory: 66100kb
Test #15:
score: 0
Accepted
time: 200ms
memory: 66104kb
Test #16:
score: 0
Accepted
time: 208ms
memory: 74708kb
Test #17:
score: 0
Accepted
time: 203ms
memory: 66328kb
Test #18:
score: 0
Accepted
time: 198ms
memory: 66100kb
Test #19:
score: 0
Accepted
time: 209ms
memory: 66100kb
Test #20:
score: 0
Accepted
time: 195ms
memory: 66032kb
Test #21:
score: 0
Accepted
time: 202ms
memory: 66096kb
Test #22:
score: 0
Accepted
time: 195ms
memory: 66332kb
Test #23:
score: 0
Accepted
time: 193ms
memory: 66032kb
Test #24:
score: -100
Wrong Answer
time: 850ms
memory: 78388kb