oj.uz

Submission #771285

# Submission time Handle Problem Language Result Execution time Memory
771285 2023-07-02T19:16:31 Z MilosMilutinovic Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 297 ms 20636 KB 
#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);
    assert(false);
}
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

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:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d%d%d%d", &l[i], &d[i], &r[i], &u[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Runtime error 2 ms 852 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Runtime error 2 ms 724 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 262 ms 20636 KB Output is correct
6 Correct 297 ms 20552 KB Output is correct
7 Correct 287 ms 17504 KB Output is correct
8 Correct 253 ms 20508 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Runtime error 2 ms 852 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Runtime error 2 ms 724 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -