oj.uz

Submission #648138

# Submission time Handle Problem Language Result Execution time Memory
648138 2022-10-05T13:46:01 Z 406 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 1815 ms 53116 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 50;
const int M = 2 * N + 5;
int l[N], r[N], u[N], d[N], n, k;
bitset<N> used, full;
vector<pair<int, int>> points;
vector<int> X, Y, cl[M], op[M];

inline bool check() {
        return used == full;
}

inline bool inter(int i, int x, int y) {
        return l[i] <= x && x <= r[i] && d[i] <= y && y <= u[i];
}

void rec(int x) {
        if (check()) {
                for (int i = 0; i < (int) points.size(); i++)
                        cout << X[points[i].first] << ' ' << Y[points[i].second] << '\n';
                for (int i = points.size(); i < k; i++)
                        cout << 1 << ' ' << 1 << '\n';
                exit(0);
        }
        if (x == k)
                return;

        for (int i = 0; i <= 2 * n; i++)
                op[i].clear(), cl[i].clear();

        int minR = 2 * n;
        for (int i = 0; i < n; i++) if (!used[i])
                minR = min(minR, r[i]);

        for (int i = 0; i < n; i++) if (!used[i] && l[i] <= minR) {
                cl[u[i]].push_back(i);
                op[d[i]].push_back(i);
        }

        set<int> S;
        vector<int> p;
        for (int h = 0; h <= 2 * n; h++) {
                for (auto u: op[h])
                        S.insert(u);
                for (auto v: cl[h]) {
                        if (S.count(v)) {
                                p.push_back(h);
                                S.clear();
                        }
                }
        }
        assert(S.empty());

        for (int h = 2 * n; h >= 0; h--) {
                for (auto u: cl[h])
                        S.insert(u);
                for (auto v: op[h]) {
                        if (S.count(v)) {
                                p.push_back(h);
                                S.clear();
                        }
                }
        }

        for (auto h: p) {
                vector<int> change;
                for (int i = 0; i < n; i++) if (!used[i]) {
                        if (inter(i, minR, h)) {
                                used[i] = true;
                                change.push_back(i);
                        }
                }
                points.emplace_back(minR, h);
                rec(x + 1);

                //RESET:
                for (auto cc: change) used[cc] = false;
                points.pop_back();
        }
}

signed main() {
        ios::sync_with_stdio(0);
        cin.tie(0);

        cin >> n >> k;
        X.reserve(2 * n), Y.reserve(2 * n);
        for (int i = 0; i < n; i++) {
                cin >> l[i] >> d[i] >> r[i] >> u[i];
                X.push_back(l[i]);
                X.push_back(r[i]);
                Y.push_back(d[i]);
                Y.push_back(u[i]);
        }
        sort(X.begin(), X.end());
        X.resize(unique(X.begin(), X.end()) - X.begin());

        sort(Y.begin(), Y.end());
        Y.resize(unique(Y.begin(), Y.end()) - Y.begin());

        for (int i = 0; i < n; i++) {
                l[i] = lower_bound(X.begin(), X.end(), l[i]) - X.begin();
                r[i] = lower_bound(X.begin(), X.end(), r[i]) - X.begin();

                u[i] = lower_bound(Y.begin(), Y.end(), u[i]) - Y.begin();
                d[i] = lower_bound(Y.begin(), Y.end(), d[i]) - Y.begin();
        }

        for (int i = 0; i < n; i++)
                full[i] = true;
        used = 0;

        rec(0);
        cout << "NO I DID NOT FIND ANYTHING\n";
        return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19412 KB Output is correct
2 Correct 13 ms 19412 KB Output is correct
3 Correct 13 ms 19460 KB Output is correct
4 Correct 13 ms 19348 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19356 KB Output is correct
2 Correct 17 ms 19412 KB Output is correct
3 Correct 14 ms 19356 KB Output is correct
4 Correct 13 ms 19412 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19360 KB Output is correct
2 Correct 14 ms 19400 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 13 ms 19412 KB Output is correct
5 Correct 16 ms 19412 KB Output is correct
6 Correct 14 ms 19412 KB Output is correct
7 Correct 14 ms 19352 KB Output is correct
8 Correct 15 ms 19396 KB Output is correct
9 Correct 15 ms 19412 KB Output is correct
10 Correct 19 ms 19352 KB Output is correct
11 Correct 17 ms 19608 KB Output is correct
12 Correct 18 ms 19416 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19284 KB Output is correct
2 Correct 16 ms 19412 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 13 ms 19396 KB Output is correct
6 Correct 13 ms 19412 KB Output is correct
7 Correct 13 ms 19408 KB Output is correct
8 Correct 13 ms 19312 KB Output is correct
9 Correct 14 ms 19376 KB Output is correct
10 Correct 16 ms 19356 KB Output is correct
11 Correct 17 ms 19412 KB Output is correct
12 Correct 14 ms 19412 KB Output is correct
13 Correct 23 ms 19428 KB Output is correct
14 Correct 22 ms 19380 KB Output is correct
15 Correct 26 ms 19412 KB Output is correct
16 Correct 86 ms 19476 KB Output is correct
17 Correct 30 ms 19436 KB Output is correct
18 Correct 35 ms 19388 KB Output is correct
19 Correct 19 ms 19412 KB Output is correct
20 Correct 30 ms 19412 KB Output is correct
21 Incorrect 111 ms 19460 KB Expected integer, but "NO" found
22 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19412 KB Output is correct
2 Correct 13 ms 19412 KB Output is correct
3 Correct 13 ms 19460 KB Output is correct
4 Correct 13 ms 19348 KB Output is correct
5 Correct 641 ms 47348 KB Output is correct
6 Correct 589 ms 47356 KB Output is correct
7 Correct 631 ms 47340 KB Output is correct
8 Correct 603 ms 47368 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19356 KB Output is correct
2 Correct 17 ms 19412 KB Output is correct
3 Correct 14 ms 19356 KB Output is correct
4 Correct 13 ms 19412 KB Output is correct
5 Correct 635 ms 41992 KB Output is correct
6 Correct 781 ms 45132 KB Output is correct
7 Correct 707 ms 50936 KB Output is correct
8 Correct 768 ms 50904 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19360 KB Output is correct
2 Correct 14 ms 19400 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 13 ms 19412 KB Output is correct
5 Correct 16 ms 19412 KB Output is correct
6 Correct 14 ms 19412 KB Output is correct
7 Correct 14 ms 19352 KB Output is correct
8 Correct 15 ms 19396 KB Output is correct
9 Correct 15 ms 19412 KB Output is correct
10 Correct 19 ms 19352 KB Output is correct
11 Correct 17 ms 19608 KB Output is correct
12 Correct 18 ms 19416 KB Output is correct
13 Correct 620 ms 49576 KB Output is correct
14 Correct 753 ms 50948 KB Output is correct
15 Correct 632 ms 48620 KB Output is correct
16 Correct 743 ms 52332 KB Output is correct
17 Correct 574 ms 48992 KB Output is correct
18 Correct 736 ms 53116 KB Output is correct
19 Correct 628 ms 49180 KB Output is correct
20 Correct 760 ms 48672 KB Output is correct
21 Correct 1059 ms 48916 KB Output is correct
22 Correct 1423 ms 48412 KB Output is correct
23 Correct 1627 ms 49524 KB Output is correct
24 Correct 1815 ms 50444 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19284 KB Output is correct
2 Correct 16 ms 19412 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 13 ms 19396 KB Output is correct
6 Correct 13 ms 19412 KB Output is correct
7 Correct 13 ms 19408 KB Output is correct
8 Correct 13 ms 19312 KB Output is correct
9 Correct 14 ms 19376 KB Output is correct
10 Correct 16 ms 19356 KB Output is correct
11 Correct 17 ms 19412 KB Output is correct
12 Correct 14 ms 19412 KB Output is correct
13 Correct 23 ms 19428 KB Output is correct
14 Correct 22 ms 19380 KB Output is correct
15 Correct 26 ms 19412 KB Output is correct
16 Correct 86 ms 19476 KB Output is correct
17 Correct 30 ms 19436 KB Output is correct
18 Correct 35 ms 19388 KB Output is correct
19 Correct 19 ms 19412 KB Output is correct
20 Correct 30 ms 19412 KB Output is correct
21 Incorrect 111 ms 19460 KB Expected integer, but "NO" found
22 Halted 0 ms 0 KB -