QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372158#2434. Single Cut of FailureUFRJ#WA 1ms4036kbC++202.4kb2024-03-31 00:17:182024-03-31 00:17:19

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 00:17:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4036kb
  • [2024-03-31 00:17:18]
  • 提交

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