oj.uz

Submission #223772

# Submission time Handle Problem Language Result Execution time Memory
223772 2020-04-16T12:04:25 Z Minnakhmetov Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 956 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 4e5 + 5;

struct R {
    int xl, yl, xr, yr;

    bool contains(int x, int y) const {
        return x >= xl && x <= xr && y >= yl && y <= yr;
    }
};

vector<R> rcs;
vector<int> vx, vy;
vector<pair<int, int>> ans;

bool solve_for_line(vector<pair<int, int>> v, int k, bool hor, int x) {
    sort(all(v));
    int last = N;
    vector<int> w;
    for (int i = v.size() - 1; i >= 0; i--) {
        if (v[i].second < last) {
            if (k == 0)
                return false;
            k--;
            last = v[i].first;
            w.push_back(last);
        }
    }
    for (int y : w) {
        ans.push_back(hor ? make_pair(y, x) : make_pair(x, y));
    }
    return true;
}

vector<R> remove_covered(vector<R> v, int x, int y) {
    vector<R> nv;
    for (const R &rc : v) {
        if (!rc.contains(x, y)) {
            nv.push_back(rc);
        }
    }
    return nv;
}

bool solve(vector<R> v, int k) {
    int mn_xr = N, mx_xl = -1, mn_yr = N, mx_yl = -1;

    for (R &rc : v) {
        mn_xr = min(mn_xr, rc.xr);
        mn_yr = min(mn_yr, rc.yr);
        mx_xl = max(mx_xl, rc.xl);
        mx_yl = max(mx_yl, rc.yl);
    }

    // cout << mn_xr << " " << mn_yr << " " << mx_xl << " " << mx_yl << "\n";

    // exit(0);

    if (mn_xr >= mx_xl && mn_yr >= mx_yl) {
        ans.push_back({mn_xr, mn_yr});
        return true;
    }
    else if (mn_xr >= mx_xl) {
        vector<pair<int, int>> sgs;
        for (R &rc : v) {
            sgs.push_back({rc.yl, rc.yr});
        }
        if (solve_for_line(sgs, k, false, mn_xr))
            return true;
        return false;
    }
    else if (mn_yr >= mx_yl) {
        vector<pair<int, int>> sgs;
        for (R &rc : v) {
            sgs.push_back({rc.xl, rc.xr});
        }
        if (solve_for_line(sgs, k, true, mn_yr))
            return true;
        return false;
    }
    else if (k == 2) {
        for (int y : {mn_yr, mx_yl}) {
            if (solve(remove_covered(v, mn_xr, y), k - 1)) {
                ans.push_back({mn_xr, y});
                return true;
            }
        }
        return false;
    }
    else {
        for (int x : {mn_xr, mx_xl}) {
            for (int y : {mn_yr, mx_yl}) {
                if (solve(remove_covered(v, x, y), k - 1)) {
                    ans.push_back({x, y});
                    return true;
                }
            }
        }
        if (k == 3)
            return false;
        assert(k == 4);
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        R r;
        cin >> r.xl >> r.yl >> r.xr >> r.yr;
        vx.push_back(r.xl);
        vx.push_back(r.xr);
        vy.push_back(r.yl);
        vy.push_back(r.yr);
        rcs.push_back(r);
    }

    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());
    sort(all(vy));
    vy.erase(unique(all(vy)), vy.end());

    for (int i = 0; i < n; i++) {
        rcs[i].xl = lower_bound(all(vx), rcs[i].xl) - vx.begin();
        rcs[i].xr = lower_bound(all(vx), rcs[i].xr) - vx.begin();
        rcs[i].yl = lower_bound(all(vy), rcs[i].yl) - vy.begin();
        rcs[i].yr = lower_bound(all(vy), rcs[i].yr) - vy.begin();
    }

    solve(rcs, k);

    if (ans.size() < k)
        ans.push_back({0, 0});

    for (auto p : ans) {
        cout << vx[p.first] << " " << vy[p.second] << "\n";
    }

    return 0;
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:142:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |     if (ans.size() < k)
      |         ~~~~~~~~~~~^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Runtime error 898 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Runtime error 849 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Runtime error 956 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 350 ms 11392 KB Output is correct
6 Correct 351 ms 11336 KB Output is correct
7 Correct 364 ms 11388 KB Output is correct
8 Correct 326 ms 11336 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Runtime error 898 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Runtime error 849 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Runtime error 956 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -