Submission #771284

#	Time	Username	Problem	Language	Result	Execution time	Memory
771284		MilosMilutinovic	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	275 ms	20676 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1e9;
int n, k, l[N], d[N], r[N], u[N];
vector<int> sweep_line(int* a, int* b) {
    vector<array<int, 3>> ev;
    for (int i = 1; i <= n; i++) {
        ev.push_back({a[i], 0, i});
        ev.push_back({b[i], 1, i});
    }
    sort(ev.begin(), ev.end());
    set<int> st;
    int bal = 0;
    vector<int> res;
    for (auto& p : ev) {
        if (p[1] == 0) {
            bal += 1;
            st.insert(p[2]);
        } else {
            bal -= 1;
            if (st.find(p[2]) != st.end()) {
                res.push_back(p[0]);
                st.clear();
            }
        }
    }
    return res;
}
void print(vector<pair<int, int>> ans) {
    while (ans.size() < k) {
        ans.emplace_back(inf, inf);
    }
    for (auto& p : ans) {
        printf("%d %d\n", p.first, p.second);
    }
}
void brute(vector<int> xs, vector<int> ys) {
    bool swp = false;
    if (xs.size() < ys.size())
        swp = true, swap(xs, ys);
    if (swp) {
        for (int i = 1; i <= n; i++) {
            swap(l[i], d[i]);
            swap(r[i], u[i]);
        }
    }
    vector<int> ans;
    auto check = [&]() {
        for (int i = 1; i <= n; i++) {
            bool ok = false;
            for (int j = 0; j < xs.size(); j++) {
                if (!(l[i] <= xs[j] && xs[j] <= r[i])) continue;
                if (!(d[i] <= ans[j] && ans[j] <= u[i])) continue;
                ok = true;
            }
            if (!ok) return false;
        }
        return true;
    };
    function<void(int)> dfs = [&](int i) {
        if (i == xs.size()) {
            if (check()) {
                vector<pair<int, int>> res;
                for (int i = 0; i < xs.size(); i++) {
                    if (!swp)
                        res.emplace_back(xs[i], ans[i]);
                    else
                        res.emplace_back(ans[i], xs[i]);
                }
                print(res);
                exit(0);
            }
            return;
        }
        for (int v : ys) {
            ans.push_back(v);
            dfs(i + 1);
            ans.pop_back();
        }
    };
    dfs(0);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &l[i], &d[i], &r[i], &u[i]);
    }
    vector<int> xs = sweep_line(l, r);
    vector<int> ys = sweep_line(d, u);
//    printf("xs = "); for (int v : xs) printf("%d ", v); printf("\n");
//    printf("ys = "); for (int v : ys) printf("%d ", v); printf("\n");
    brute(xs, ys);
    return 0;
    printf("%d %d\n", xs[0], ys[0]);
}

Compilation message (stderr)

hamburg.cpp: In function 'void print(std::vector<std::pair<int, int> >)':
hamburg.cpp:31: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]
   31 |     while (ans.size() < k) {
      |            ~~~~~~~~~~~^~~
hamburg.cpp: In lambda function:
hamburg.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int j = 0; j < xs.size(); j++) {
      |                             ~~^~~~~~~~~~~
hamburg.cpp: In lambda function:
hamburg.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (i == xs.size()) {
      |             ~~^~~~~~~~~~~~
hamburg.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for (int i = 0; i < xs.size(); i++) {
      |                                 ~~^~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d%d%d%d", &l[i], &d[i], &r[i], &u[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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