Submission #1048800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048800		kostia244	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	168 ms	36460 KiB

hamburg

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

const int inf = 1<<30;
struct Rect {
    array<array<int, 2>, 2> ranges;
    void rotate(int c) {
        while(c--) {
            for(int i = 0; i < 2; i++) {
                ranges[0][i] = -exchange(ranges[1][i], ranges[0][i]);
            }
            for(int i = 0; i < 2; i++) {
                if(ranges[i][0] > ranges[i][1])
                    swap(ranges[i][0], ranges[i][1]);
            }
        }
    }
    friend Rect intersect(const Rect &a, const Rect &b) {
        Rect res;
        for(int i = 0; i < 2; i++) {
            res.ranges[i][0] = max(a.ranges[i][0], b.ranges[i][0]);
            res.ranges[i][1] = min(a.ranges[i][1], b.ranges[i][1]);
        }
        return res;
    }
    bool contains(array<int, 2> P) {
        for(int i = 0; i < 2; i++) {
            if(P[i] < ranges[i][0] || P[i] > ranges[i][1])
                return false;
        }
        return true;
    }
};

Rect intersectAll(vector<Rect> &v) {
    Rect res;
    res.ranges[0][0] = res.ranges[1][0] = -inf;
    res.ranges[0][1] = res.ranges[1][1] = inf;
    for(auto &i : v)
        res = intersect(res, i);
    return res;
}
vector<Rect> prune(vector<Rect> v, array<int, 2> P) {
    vector<Rect> res;
    for(auto i : v) if(!i.contains(P)) {
        res.push_back(i);
    }
    return res;
}

// Solve k<=3 and k=4 if we use a corner or intersection is non-empty
vector<array<int, 2>> solve_corner(vector<Rect> rects, int k) {
    if(k < 1) return {};
    
    //All intersect use 1, not tested
    Rect I = intersectAll(rects);
    if(I.ranges[0][0] <= I.ranges[0][1] && I.ranges[1][0] <= I.ranges[1][1]) {
        return {{I.ranges[0][0], I.ranges[1][0]}};
    }
    
    // for(auto &c : I.ranges) {
    //     for(auto &v : c) cout << v << ", ";
    //     cout << endl;
    // }
    //1D case; not tested
    int rot = 0;
    if(I.ranges[1][0] <= I.ranges[1][1]) {
        rot++;
        I.rotate(1);
        for(auto &i : rects) i.rotate(1);
    }
    if(I.ranges[0][0] <= I.ranges[0][1]) {
        vector<array<int, 2>> segs;//{R, L}
        for(auto r : rects) {
            segs.push_back({r.ranges[1][1], r.ranges[1][0]});
        }
        sort(all(segs));
        int covered = -1;
        vector<array<int, 2>> sol;
        for(auto [r, l] : segs) {
            if(l <= covered) {
                assert(covered <= r);
            } else {
                sol.push_back({I.ranges[0][0], covered = r});
            }
        }
        if(sol.size() > k) return {};
        if(rot) {
            for(auto &[x, y] : sol) {
                y = -exchange(x, y);
            }
        }
        return sol;
    }
    
    assert(!rot);
    
    //Use corner case; not tested
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            array<int, 2> P = {I.ranges[0][i], I.ranges[1][j]};
            auto tmp = solve_corner(prune(rects, P), k - 1);
            if(!tmp.empty()) {
                tmp.push_back(P);
                return tmp;
            }
        }
    }
    
    return {};
}

//solve k=4, no point in the corner -> all on the perimeter
vector<array<int, 2>> solve_perim(vector<Rect> rects) {
    return {};
}

vector<array<int, 2>> solve() {
    int n, k;
    cin >> n >> k;
    vector<Rect> rects(n);
    for(auto &r : rects) {
        // cin >> r.ranges[0][0] >> r[1][0] >> r[0][1] >> r[1][1];
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                cin >> r.ranges[j][i];
        
    }
    
    auto res = solve_corner(rects, k);
    if(res.empty() && k == 4) {
        res = solve_perim(rects);
    }
    assert(!res.empty());
    while(res.size() < k) res.push_back(res.back());

    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    auto out = solve();
    for(auto [x, y] : out) {
        cout << x << " " << y << '\n';
    }
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve_corner(std::vector<Rect>, int)':
hamburg.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(sol.size() > k) return {};
      |            ~~~~~~~~~~~^~~
hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve()':
hamburg.cpp:137:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |     while(res.size() < k) res.push_back(res.back());
      |           ~~~~~~~~~~~^~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79