oj.uz

Submission #223777

# Submission time Handle Problem Language Result Execution time Memory
223777 2020-04-16T12:22:22 Z Minnakhmetov Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 396 ms 26924 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 = (int)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 if (k >= 2) {
        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);

    while (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:23: 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 |     while (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 3 ms 456 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #2
1.0 / 1.0

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

Subtask #3
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 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Incorrect 4 ms 640 KB Output isn't correct
15 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 3 ms 456 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 319 ms 10004 KB Output is correct
6 Correct 332 ms 10008 KB Output is correct
7 Correct 371 ms 10032 KB Output is correct
8 Correct 319 ms 10052 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 560 KB Output is correct
2 Correct 4 ms 624 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 361 ms 17544 KB Output is correct
6 Correct 360 ms 17428 KB Output is correct
7 Correct 337 ms 17476 KB Output is correct
8 Correct 350 ms 20420 KB Output is correct

Subtask #7
6.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 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 372 ms 14788 KB Output is correct
14 Correct 379 ms 14788 KB Output is correct
15 Correct 363 ms 14784 KB Output is correct
16 Correct 374 ms 14716 KB Output is correct
17 Correct 352 ms 14792 KB Output is correct
18 Correct 373 ms 14948 KB Output is correct
19 Correct 396 ms 19712 KB Output is correct
20 Correct 329 ms 20976 KB Output is correct
21 Correct 390 ms 26924 KB Output is correct
22 Correct 371 ms 21292 KB Output is correct
23 Correct 372 ms 25028 KB Output is correct
24 Correct 389 ms 26180 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Incorrect 4 ms 640 KB Output isn't correct
15 Halted 0 ms 0 KB -