oj.uz

Submission #896224

# Submission time Handle Problem Language Result Execution time Memory
896224 2024-01-01T03:09:53 Z box Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 183 ms 12892 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; bug_h(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int INF = 1e9;

int N, K;
vector<ar<int, 4>> rect;
vector<bool> covered;
vector<pi> solutions;

ar<int, 4> get_bounds() {
    int x1 = INF, x2 = 1, y1 = INF, y2 = 1;
    for (int i = 0; i < N; i++) if (!covered[i]) {
        auto [l, d, r, u] = rect[i];
        x1 = min(x1, r);
        x2 = max(x2, l);
        y1 = min(y1, u);
        y2 = max(y2, d);
    }
    return {x1, x2, y1, y2};
}

void pr() {
    for (auto [x, y] : solutions) cout << x << ' ' << y << '\n';
    exit(0);
}

void rec(int k) {
    if (!k) {
        if (count(begin(covered), end(covered), 1) == N) pr();
        return;
    }
    auto [x1, x2, y1, y2] = get_bounds();
    for (auto x : {x1, x2}) for (auto y : {y1, y2}) {
        solutions.push_back({x, y});
        vector<int> add;
        for (int i = 0; i < N; i++) if (!covered[i]) {
            auto [l, d, r, u] = rect[i];
            if (l <= x && x <= r && d <= y && y <= u) add.push_back(i);
        }
        for (int i : add) covered[i] = 1;
        rec(k - 1);
        for (int i : add) covered[i] = 0;
        solutions.pop_back();
    }
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    rect.resize(N);
    for (auto &[l, d, r, u] : rect) {
        cin >> l >> d >> r >> u;
    }
    covered.resize(N);
    rec(K);
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 6 ms 352 KB Output is correct
14 Incorrect 6 ms 352 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 61 ms 4744 KB Output is correct
6 Correct 62 ms 4744 KB Output is correct
7 Correct 62 ms 12500 KB Output is correct
8 Correct 64 ms 12500 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 65 ms 12496 KB Output is correct
6 Correct 73 ms 12756 KB Output is correct
7 Correct 65 ms 12396 KB Output is correct
8 Correct 78 ms 12616 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 67 ms 12408 KB Output is correct
14 Correct 69 ms 12296 KB Output is correct
15 Correct 70 ms 12632 KB Output is correct
16 Correct 65 ms 12408 KB Output is correct
17 Correct 66 ms 12500 KB Output is correct
18 Correct 66 ms 12500 KB Output is correct
19 Correct 67 ms 12456 KB Output is correct
20 Correct 80 ms 12400 KB Output is correct
21 Correct 183 ms 12892 KB Output is correct
22 Correct 144 ms 12304 KB Output is correct
23 Correct 105 ms 12436 KB Output is correct
24 Correct 111 ms 12544 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 6 ms 352 KB Output is correct
14 Incorrect 6 ms 352 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -