QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372178#2434. Single Cut of FailureUFRJAC ✓5335ms323764kbC++202.4kb2024-03-31 02:32:282024-03-31 02:32:29

Judging History

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

  • [2024-03-31 02:32:29]
  • 评测
  • 测评结果:AC
  • 用时:5335ms
  • 内存:323764kb
  • [2024-03-31 02:32:28]
  • 提交

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;
}

详细

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