oj.uz

Submission #1000064

# Submission time Handle Problem Language Result Execution time Memory
1000064 2024-06-16T14:45:00 Z Unforgettablepl Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 1079 ms 39672 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;
}

bool strat3(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);
    }
    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 true;
    }
    iter++;
    if(iter==1)currpoint={minR,maxD};
    else if(iter==2)currpoint={maxL,minU};
    else if(iter==3)currpoint={maxL,maxD};
    else return false;
    goto t;
}

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);
    vector<pair<int,int>> points;
    for(auto&[a,b]:rect){
        cin >> a.first >> b.first >> a.second >> b.second;
        points.emplace_back(a.first,b.first);
        points.emplace_back(a.first,b.second);
        points.emplace_back(a.second,b.first);
        points.emplace_back(a.second,b.second);
    }
    if(k==2){
        strat2(rect);
        return 0;
    }
    if(k==3){
        strat3(rect);
        return 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&p:points){
        vector<pair<pair<int,int>,pair<int,int>>> newrect;
        for(auto&i:rect)if(!intersect(p,i))newrect.push_back(i);
        if(strat3(newrect)){
            cout << p.first << ' ' << p.second << '\n';
            return 0;
        }
    }
}

Compilation message

hamburg.cpp: In function 'int32_t main()':
hamburg.cpp:79:9: warning: unused variable 'minR' [-Wunused-variable]
   79 |     int minR = 1e9,minU = 1e9,maxL = 1,maxD = 1;
      |         ^~~~
hamburg.cpp:79:20: warning: unused variable 'minU' [-Wunused-variable]
   79 |     int minR = 1e9,minU = 1e9,maxL = 1,maxD = 1;
      |                    ^~~~
hamburg.cpp:79:31: warning: unused variable 'maxL' [-Wunused-variable]
   79 |     int minR = 1e9,minU = 1e9,maxL = 1,maxD = 1;
      |                               ^~~~
hamburg.cpp:79:40: warning: unused variable 'maxD' [-Wunused-variable]
   79 |     int minR = 1e9,minU = 1e9,maxL = 1,maxD = 1;
      |                                        ^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 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 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 724 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 604 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 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 856 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 Correct 42 ms 868 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 410 ms 944 KB Output is correct
4 Correct 290 ms 3120 KB Output is correct
5 Correct 81 ms 960 KB Output is correct
6 Correct 25 ms 940 KB Output is correct
7 Incorrect 1079 ms 968 KB Unexpected end of file - int32 expected
8 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 52 ms 348 KB Output is correct
6 Correct 64 ms 344 KB Output is correct
7 Correct 52 ms 348 KB Output is correct
8 Correct 55 ms 348 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 86 ms 25252 KB Output is correct
6 Correct 68 ms 25464 KB Output is correct
7 Correct 76 ms 25264 KB Output is correct
8 Correct 69 ms 25276 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 724 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 604 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 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 69 ms 32436 KB Output is correct
14 Correct 70 ms 32152 KB Output is correct
15 Correct 67 ms 29360 KB Output is correct
16 Correct 71 ms 29368 KB Output is correct
17 Correct 70 ms 32448 KB Output is correct
18 Correct 69 ms 28856 KB Output is correct
19 Correct 69 ms 32948 KB Output is correct
20 Correct 69 ms 32932 KB Output is correct
21 Correct 95 ms 39672 KB Output is correct
22 Correct 90 ms 33440 KB Output is correct
23 Correct 86 ms 38216 KB Output is correct
24 Correct 75 ms 39332 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 868 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 410 ms 944 KB Output is correct
4 Correct 290 ms 3120 KB Output is correct
5 Correct 81 ms 960 KB Output is correct
6 Correct 25 ms 940 KB Output is correct
7 Incorrect 1079 ms 968 KB Unexpected end of file - int32 expected
8 Halted 0 ms 0 KB -