oj.uz

Submission #787374

# Submission time Handle Problem Language Result Execution time Memory
787374 2023-07-19T06:33:35 Z 이동현(#10034) Hamburg Steak (JOI20_hamburg) C++17
0 / 100
 4 ms 2004 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, a[i][2]);
            yl = min(yl, a[i][3]);
            yr = max(yr, a[i][1]);
        }

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

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

    assert(false);

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Runtime error 4 ms 2004 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1308 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 2 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Runtime error 4 ms 2004 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

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