QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372178 | #2434. Single Cut of Failure | UFRJ | AC ✓ | 5335ms | 323764kb | C++20 | 2.4kb | 2024-03-31 02:32:28 | 2024-03-31 02:32:29 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using lint = int64_t;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<lint>uid(1, 1e18);
int main(void) {
cin.tie(nullptr)->sync_with_stdio(false);
int n, w, h;
cin>>n>>w>>h;
map<int, pair<int, int>>back;
auto id = [&](int x, int y)->int {
int res = -1;
if(y == 0) res = x;
else if(x == w) res = w + y - 0;
else if(y == h) res = w + h + (w - x);
else res = w + h + w + (h - y);
back[res] = {x, y};
return res;
};
vector<int>x1(n), y1(n), x2(n), y2(n), a(n), b(n);
for(int i=0;i<n;i++){
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
a[i] = id(x1[i], y1[i]);
b[i] = id(x2[i], y2[i]);
if(a[i] > b[i]) swap(a[i], b[i]);
}
vector<int>v;
for(int i=0;i<n;i++){
v.push_back(a[i]);
v.push_back(b[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int &u : a) u = int(lower_bound(v.begin(), v.end(), u) - v.begin());
for(int &u : b) u = int(lower_bound(v.begin(), v.end(), u) - v.begin());
vector<lint>hash(n);
lint tot = 0;
for(int i=0;i<n;i++) hash[i] = uid(rng), tot ^= hash[i];
int sz = v.size();
vector<lint>upd(sz);
for(int i=0;i<n;i++) upd[a[i]] ^= hash[i];
for(int i=0;i<n;i++) upd[b[i]] ^= hash[i];
vector<lint>pref(sz + 1);
for(int i=0;i<sz;i++) pref[i+1] = pref[i] ^ upd[i];
map<lint, int>last;
int l = -1, r = -1;
for(int i=1;i<=sz;i++){
if(last.count(tot ^ pref[i])){
l = last[tot ^ pref[i]];
r = i - 1;
break;
}
last[pref[i]] = i - 1;
}
cout<<fixed<<setprecision(1);
if(l == -1){
cout<<"2\n";
cout<<0<<" 0.5"<<" ";
cout<<w<<" "<<h-0.5<<"\n";
cout<<0<<" "<<h-0.5<<" ";
cout<<w<<" "<<0.5<<"\n";
return 0;
}
auto [X1, Y1] = back[v[l]];
auto [X2, Y2] = back[v[r]];
double ax1 = X1, ay1 = Y1;
double ax2 = X2, ay2 = Y2;
if(Y1 == 0) ax1 += 0.5;
else if(X1 == w) ay1 += 0.5;
else if(Y1 == h) ax1 -= 0.5;
else ay1 -= 0.5;
if(Y2 == 0) ax2 += 0.5;
else if(X2 == w) ay2 += 0.5;
else if(Y2 == h) ax2 -= 0.5;
else ay2 -= 0.5;
cout<<"1\n";
cout<<ax1<<" "<<ay1<<" "<<ax2<<" "<<ay2<<"\n";
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 4028kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3892kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3920kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3780kb
Test #9:
score: 0
Accepted
time: 667ms
memory: 67556kb
Test #10:
score: 0
Accepted
time: 691ms
memory: 67628kb
Test #11:
score: 0
Accepted
time: 657ms
memory: 75488kb
Test #12:
score: 0
Accepted
time: 555ms
memory: 67724kb
Test #13:
score: 0
Accepted
time: 638ms
memory: 67788kb
Test #14:
score: 0
Accepted
time: 755ms
memory: 83592kb
Test #15:
score: 0
Accepted
time: 650ms
memory: 67728kb
Test #16:
score: 0
Accepted
time: 509ms
memory: 67572kb
Test #17:
score: 0
Accepted
time: 827ms
memory: 83592kb
Test #18:
score: 0
Accepted
time: 698ms
memory: 67656kb
Test #19:
score: 0
Accepted
time: 808ms
memory: 83644kb
Test #20:
score: 0
Accepted
time: 698ms
memory: 75544kb
Test #21:
score: 0
Accepted
time: 821ms
memory: 83676kb
Test #22:
score: 0
Accepted
time: 715ms
memory: 67672kb
Test #23:
score: 0
Accepted
time: 635ms
memory: 71528kb
Test #24:
score: 0
Accepted
time: 4082ms
memory: 292172kb
Test #25:
score: 0
Accepted
time: 4892ms
memory: 323644kb
Test #26:
score: 0
Accepted
time: 0ms
memory: 3752kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3880kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3864kb
Test #29:
score: 0
Accepted
time: 5ms
memory: 4860kb
Test #30:
score: 0
Accepted
time: 49ms
memory: 11920kb
Test #31:
score: 0
Accepted
time: 4314ms
memory: 280108kb
Test #32:
score: 0
Accepted
time: 5335ms
memory: 323764kb
Test #33:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3944kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 3988kb
Test #36:
score: 0
Accepted
time: 10ms
memory: 6124kb
Test #37:
score: 0
Accepted
time: 29ms
memory: 10212kb
Test #38:
score: 0
Accepted
time: 449ms
memory: 55384kb
Test #39:
score: 0
Accepted
time: 3863ms
memory: 275596kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #41:
score: 0
Accepted
time: 1ms
memory: 4064kb
Test #42:
score: 0
Accepted
time: 1ms
memory: 3900kb
Test #43:
score: 0
Accepted
time: 7ms
memory: 6152kb
Test #44:
score: 0
Accepted
time: 158ms
memory: 27152kb
Test #45:
score: 0
Accepted
time: 3188ms
memory: 222192kb
Test #46:
score: 0
Accepted
time: 5018ms
memory: 323396kb
Test #47:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #48:
score: 0
Accepted
time: 0ms
memory: 3872kb
Test #49:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #50:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #51:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #52:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #53:
score: 0
Accepted
time: 1ms
memory: 3860kb
Test #54:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #55:
score: 0
Accepted
time: 0ms
memory: 3956kb
Test #56:
score: 0
Accepted
time: 1ms
memory: 3784kb
Test #57:
score: 0
Accepted
time: 0ms
memory: 3956kb
Test #58:
score: 0
Accepted
time: 0ms
memory: 3744kb
Test #59:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #60:
score: 0
Accepted
time: 1ms
memory: 3816kb
Test #61:
score: 0
Accepted
time: 0ms
memory: 3872kb
Test #62:
score: 0
Accepted
time: 1ms
memory: 3856kb
Test #63:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #64:
score: 0
Accepted
time: 1ms
memory: 4032kb
Test #65:
score: 0
Accepted
time: 0ms
memory: 3876kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 3920kb
Test #67:
score: 0
Accepted
time: 0ms
memory: 4036kb
Test #68:
score: 0
Accepted
time: 0ms
memory: 3816kb
Test #69:
score: 0
Accepted
time: 0ms
memory: 3788kb
Test #70:
score: 0
Accepted
time: 0ms
memory: 3956kb
Test #71:
score: 0
Accepted
time: 152ms
memory: 29096kb
Test #72:
score: 0
Accepted
time: 155ms
memory: 29104kb
Test #73:
score: 0
Accepted
time: 158ms
memory: 31956kb
Test #74:
score: 0
Accepted
time: 184ms
memory: 35208kb
Test #75:
score: 0
Accepted
time: 156ms
memory: 31992kb
Test #76:
score: 0
Accepted
time: 1ms
memory: 3960kb