oj.uz

Submission #787377

# Submission time Handle Problem Language Result Execution time Memory
787377 2023-07-19T06:35:58 Z 이동현(#10034) Hamburg Steak (JOI20_hamburg) C++17
9 / 100
 291 ms 72952 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(4));
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    }

    auto chk = [&](vector<vector<int>> x, vector<vector<int>> pos){
        for(int i = 0; i < (int)x.size(); ++i){
            int ok = 0;
            for(auto&j:pos){
                if(j[0] >= x[i][0] && j[0] <= x[i][2] && j[1] >= x[i][1] && j[1] <= x[i][3]){
                    ok = 1;
                    break;
                }
            }
            if(!ok) return 0;
        }
        return 1;
    };

    auto solve1 = [&](vector<vector<int>> x)->vector<int>{
        int xp = 1, yp = 1;
        for(int i = 0; i < (int)x.size(); ++i){
            xp = max(xp, x[i][0]);
            yp = max(yp, x[i][1]);
        }

        if(chk(x, {{xp, yp}})){
            return {1, xp, yp};
        }
        return {0};
    };

    int xu = (int)2e9, xd = -1, yl = (int)2e9, yr = -1;
    for(int i = 0; i < n; ++i){
        xu = min(xu, a[i][2]);
        xd = max(xd, a[i][0]);
        yl = min(yl, a[i][3]);
        yr = max(yr, a[i][1]);
    }

    auto solveline = [&](vector<vector<int>> x){
        vector<int> rv;
        sort(x.begin(), x.end(), [&](vector<int>&a, vector<int>&b){return a[1] < b[1];});
        for(int i = 0; i < (int)x.size(); ++i){
            if(!(int)rv.size() || rv.back() < x[i][0]){
                rv.push_back(x[i][1]);
            }
        }
        return rv;
    };

    if(xd <= xu){
        vector<vector<int>> x(n);
        for(int i = 0; i < n; ++i){
            x[i] = {a[i][1], a[i][3]};
        }
        auto rv = solveline(x);
        if((int)rv.size() <= 3){
            for(int i = 0; i < 3; ++i){
                cout << xd << ' ' << (i < (int)rv.size() ? rv[i] : rv.back()) << '\n';
            }
            return 0;
        }
    }
    if(yr <= yl){
        vector<vector<int>> x(n);
        for(int i = 0; i < n; ++i){
            x[i] = {a[i][0], a[i][2]};
        }
        auto rv = solveline(x);
        if((int)rv.size() <= 3){
            for(int i = 0; i < 3; ++i){
                cout << (i < (int)rv.size() ? rv[i] : rv.back()) << ' ' << yl << '\n';
            }
            return 0;
        }
    }

    auto solve2 = [&](vector<vector<int>> x, int px, int py, int ppx, int ppy){
        vector<vector<int>> nxt;
        for(auto&i:x){
            if(!(px >= i[0] && px <= i[2] && py >= i[1] && py <= i[3])){
                nxt.push_back(i);
            }
        }
        auto rv = solve1(nxt);
        if(rv[0] == 1){
            cout << px << ' ' << py << '\n' << rv[1] << ' ' << rv[2] << '\n' << ppx << ' ' << ppy << '\n';
            exit(0);
        }
    };

    auto solve3 = [&](vector<vector<int>> x, int px, int py){
        vector<vector<int>> nxt;
        for(auto&i:x){
            if(!(px >= i[0] && px <= i[2] && py >= i[1] && py <= i[3])){
                nxt.push_back(i);
            }
        }

        int xu = (int)2e9, yl = (int)2e9, yr = -1;
        for(int i = 0; i < (int)nxt.size(); ++i){
            xu = min(xu, nxt[i][2]);
            yl = min(yl, nxt[i][3]);
            yr = max(yr, nxt[i][1]);
        }

        solve2(nxt, xu, yl, px, py);
        solve2(nxt, xu, yr, px, py);
    };

    solve3(a, xu, yl);
    solve3(a, xu, yr);
    solve3(a, xd, yl);
    solve3(a, xd, yr);

    assert(false);

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Extra information in the output file
2 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 916 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Extra information in the output file
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 916 KB Output is correct
13 Correct 135 ms 33156 KB Output is correct
14 Correct 109 ms 33172 KB Output is correct
15 Correct 117 ms 33156 KB Output is correct
16 Correct 114 ms 33100 KB Output is correct
17 Correct 111 ms 33152 KB Output is correct
18 Correct 109 ms 33188 KB Output is correct
19 Correct 92 ms 43456 KB Output is correct
20 Correct 103 ms 46336 KB Output is correct
21 Correct 291 ms 72952 KB Output is correct
22 Correct 165 ms 51368 KB Output is correct
23 Correct 157 ms 62092 KB Output is correct
24 Correct 173 ms 72844 KB Output is correct

Subtask #8
0 / 79.0

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