QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372158 | #2434. Single Cut of Failure | UFRJ# | WA | 1ms | 4036kb | C++20 | 2.4kb | 2024-03-31 00:17:18 | 2024-03-31 00:17:19 |
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;
}
if(l == -1){
cout<<"2\n";
cout<<fixed<<setprecision(1)<<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: 3836kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3828kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 4036kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3828kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3960kb
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3868kb