oj.uz

Submission #1000062

# Submission time Handle Problem Language Result Execution time Memory
1000062 2024-06-16T14:34:19 Z Unforgettablepl Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 82 ms 28652 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
void strat1(int n){
    pair<int,int> curr_x = {1,1e9};
    pair<int,int> curr_y = {1,1e9};
    auto combine = [&](pair<int,int> a,pair<int,int> b){
        return make_pair(max(a.first,b.first),min(a.second,b.second));
    };
    for(int i=1;i<=n;i++){
        pair<int,int> x,y;
        cin >> x.first >> y.first >> x.second >> y.second;
        curr_x = combine(curr_x,x);
        curr_y = combine(curr_y,y);
    }
    cout << curr_x.first << ' ' << curr_y.first << '\n';
    exit(0);
}
 
bool strat2(vector<pair<pair<int,int>,pair<int,int>>> rect){
    int minR = 1e9,minU = 1e9,maxL = 1,maxD = 1;
    for(auto&[a,b]:rect){
        maxL = max(maxL,a.first);
        minR = min(minR,a.second);
        minU = min(minU,b.second);
        maxD = max(maxD,b.first);
    }
    int satisa = 0,satisb = 0;
    auto intersect = [&](pair<int,int> point,pair<pair<int,int>,pair<int,int>> rec){
        return rec.first.first <= point.first and point.first <=rec.first.second and rec.second.first <= point.second and point.second <= rec.second.second;
    };
    for(auto&i:rect){
        if(intersect({minR,minU},i) or intersect({maxL,maxD},i))satisa++;
        if(intersect({minR,maxD},i) or intersect({maxL,minU},i))satisb++;
    }
    int n = rect.size();
    if(satisa!=n and satisb!=n)return false;
    if(satisa==n)cout<<minR<<' '<<minU<<'\n'<<maxL<<' '<<maxD<<'\n';
    else cout<<minR<<' '<<maxD<<'\n'<<maxL<<' '<<minU<<'\n';
    return true;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    if(k==1)strat1(n);
    int minR = 1e9,minU = 1e9,maxL = 1,maxD = 1;
    vector<pair<pair<int,int>,pair<int,int>>> rect(n);
    for(auto&[a,b]:rect){
        cin >> a.first >> b.first >> a.second >> b.second;
        maxL = max(maxL,a.first);
        minR = min(minR,a.second);
        minU = min(minU,b.second);
        maxD = max(maxD,b.first);
    }
    if(k==2){
        strat2(rect);
        return 0;
    }
    assert(k==3);
    auto intersect = [&](pair<int,int> point,pair<pair<int,int>,pair<int,int>> rec){
        return rec.first.first <= point.first and point.first <=rec.first.second and rec.second.first <= point.second and point.second <= rec.second.second;
    };
    pair<int,int> currpoint = {minR,minU};
    int iter = 0;
    t:
    vector<pair<pair<int,int>,pair<int,int>>> newrect;
    for(auto&i:rect)if(!intersect(currpoint,i))newrect.push_back(i);
    if(strat2(newrect)){
        cout << currpoint.first << ' ' << currpoint.second << '\n';
        return 0;
    }
    iter++;
    if(iter==1)currpoint={minR,maxD};
    else if(iter==2)currpoint={maxL,minU};
    else currpoint={maxL,maxD};
    goto t;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 65 ms 436 KB Output is correct
6 Correct 48 ms 344 KB Output is correct
7 Correct 48 ms 348 KB Output is correct
8 Correct 53 ms 348 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 67 ms 12888 KB Output is correct
6 Correct 54 ms 12880 KB Output is correct
7 Correct 56 ms 12884 KB Output is correct
8 Correct 54 ms 12868 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 61 ms 20424 KB Output is correct
14 Correct 62 ms 19912 KB Output is correct
15 Correct 61 ms 18224 KB Output is correct
16 Correct 64 ms 18380 KB Output is correct
17 Correct 60 ms 20392 KB Output is correct
18 Correct 57 ms 17096 KB Output is correct
19 Correct 59 ms 21156 KB Output is correct
20 Correct 62 ms 21700 KB Output is correct
21 Correct 82 ms 28652 KB Output is correct
22 Correct 69 ms 22512 KB Output is correct
23 Correct 63 ms 23488 KB Output is correct
24 Correct 76 ms 26052 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -