oj.uz

Submission #1048800

# Submission time Handle Problem Language Result Execution time Memory
1048800 2024-08-08T09:34:48 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 168 ms 36460 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 476 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 568 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 468 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 2 ms 748 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 720 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 1 ms 604 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 376 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 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 3 ms 776 KB Output is correct
11 Correct 3 ms 820 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Runtime error 3 ms 1112 KB Execution killed with signal 6
15 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 476 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 45 ms 14192 KB Output is correct
6 Correct 48 ms 14420 KB Output is correct
7 Correct 44 ms 14416 KB Output is correct
8 Correct 45 ms 14420 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 568 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 49 ms 19660 KB Output is correct
6 Correct 57 ms 24008 KB Output is correct
7 Correct 50 ms 19560 KB Output is correct
8 Correct 60 ms 31432 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 468 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 2 ms 748 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 61 ms 16488 KB Output is correct
14 Correct 68 ms 16504 KB Output is correct
15 Correct 61 ms 16512 KB Output is correct
16 Correct 63 ms 16592 KB Output is correct
17 Correct 64 ms 16588 KB Output is correct
18 Correct 60 ms 16588 KB Output is correct
19 Correct 49 ms 22724 KB Output is correct
20 Correct 168 ms 36404 KB Output is correct
21 Correct 55 ms 26056 KB Output is correct
22 Correct 89 ms 35440 KB Output is correct
23 Correct 120 ms 36336 KB Output is correct
24 Correct 96 ms 36460 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 376 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 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 3 ms 776 KB Output is correct
11 Correct 3 ms 820 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Runtime error 3 ms 1112 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -