oj.uz

Submission #648331

# Submission time Handle Problem Language Result Execution time Memory
648331 2022-10-06T07:26:05 Z 406 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 3000 ms 29680 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];

void rec();

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 add_point(int x, int y) {
        vector<int> change;
        for (int i = 0; i < n; i++) if (!used[i]) {
                if (inter(i, x, y)) {
                        used[i] = true;
                        change.push_back(i);
                }
        }
        points.emplace_back(x, y);

        rec();

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

}

void rec() {
        if (check() && (int) points.size() <= k) {
                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 (points.size() >= k)
                return;

        int minR = 2 * n;
        int minU = 2 * n;
        int maxD = 0;
        int maxL = 0;

        for (int i = 0; i < n; i++) if (!used[i]) {
                minR = min(minR, r[i]);
                maxL = max(maxL, l[i]);

                minU = min(minU, u[i]);
                maxD = max(maxD, d[i]);
        }

        if (maxL <= minR) {
                add_point(minR, minU);
        }
        else if (maxD <= minU) {
                add_point(minR, minU);
        }
        else {
                add_point(minR, minU);
                add_point(minR, maxD);
                add_point(maxL, minU);
                add_point(maxL, maxD);
                if (points.size())
                        return;
                for (int h = 0; h < Y.size(); h++)
                        add_point(minR, h);
        }
}

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();
        cout << "NO I DID NOT FIND ANYTHING\n";
        return 0;
}

Compilation message

hamburg.cpp: In function 'void rec()':
hamburg.cpp:46:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if (points.size() >= k)
      |             ~~~~~~~~~~~~~~^~~~
hamburg.cpp:75:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for (int h = 0; h < Y.size(); h++)
      |                                 ~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 11 ms 19336 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 12 ms 19228 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19288 KB Output is correct
2 Correct 15 ms 19288 KB Output is correct
3 Correct 13 ms 19252 KB Output is correct
4 Correct 11 ms 19284 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19244 KB Output is correct
2 Correct 14 ms 19284 KB Output is correct
3 Correct 12 ms 19284 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 15 ms 19288 KB Output is correct
6 Correct 13 ms 19284 KB Output is correct
7 Correct 12 ms 19284 KB Output is correct
8 Correct 12 ms 19284 KB Output is correct
9 Correct 14 ms 19284 KB Output is correct
10 Correct 13 ms 19332 KB Output is correct
11 Correct 13 ms 19288 KB Output is correct
12 Correct 15 ms 19284 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19284 KB Output is correct
2 Correct 13 ms 19328 KB Output is correct
3 Correct 15 ms 19284 KB Output is correct
4 Correct 13 ms 19284 KB Output is correct
5 Correct 13 ms 19236 KB Output is correct
6 Correct 12 ms 19284 KB Output is correct
7 Correct 12 ms 19280 KB Output is correct
8 Correct 12 ms 19312 KB Output is correct
9 Correct 15 ms 19276 KB Output is correct
10 Correct 14 ms 19316 KB Output is correct
11 Correct 13 ms 19408 KB Output is correct
12 Correct 12 ms 19296 KB Output is correct
13 Correct 17 ms 19240 KB Output is correct
14 Correct 2977 ms 19344 KB Output is correct
15 Correct 17 ms 19284 KB Output is correct
16 Correct 18 ms 19284 KB Output is correct
17 Correct 2665 ms 19328 KB Output is correct
18 Correct 16 ms 19412 KB Output is correct
19 Correct 20 ms 19324 KB Output is correct
20 Execution timed out 3058 ms 19284 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 11 ms 19336 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 12 ms 19228 KB Output is correct
5 Correct 315 ms 29244 KB Output is correct
6 Correct 317 ms 29248 KB Output is correct
7 Correct 282 ms 29252 KB Output is correct
8 Correct 297 ms 29456 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19288 KB Output is correct
2 Correct 15 ms 19288 KB Output is correct
3 Correct 13 ms 19252 KB Output is correct
4 Correct 11 ms 19284 KB Output is correct
5 Correct 303 ms 29376 KB Output is correct
6 Correct 296 ms 29680 KB Output is correct
7 Correct 316 ms 29156 KB Output is correct
8 Correct 310 ms 29076 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19244 KB Output is correct
2 Correct 14 ms 19284 KB Output is correct
3 Correct 12 ms 19284 KB Output is correct
4 Correct 13 ms 19328 KB Output is correct
5 Correct 15 ms 19288 KB Output is correct
6 Correct 13 ms 19284 KB Output is correct
7 Correct 12 ms 19284 KB Output is correct
8 Correct 12 ms 19284 KB Output is correct
9 Correct 14 ms 19284 KB Output is correct
10 Correct 13 ms 19332 KB Output is correct
11 Correct 13 ms 19288 KB Output is correct
12 Correct 15 ms 19284 KB Output is correct
13 Correct 292 ms 28480 KB Output is correct
14 Correct 294 ms 28224 KB Output is correct
15 Correct 302 ms 28528 KB Output is correct
16 Correct 305 ms 28492 KB Output is correct
17 Correct 297 ms 28424 KB Output is correct
18 Correct 294 ms 28516 KB Output is correct
19 Correct 328 ms 28352 KB Output is correct
20 Correct 310 ms 28416 KB Output is correct
21 Correct 436 ms 29168 KB Output is correct
22 Correct 374 ms 29056 KB Output is correct
23 Correct 341 ms 29044 KB Output is correct
24 Correct 371 ms 29072 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19284 KB Output is correct
2 Correct 13 ms 19328 KB Output is correct
3 Correct 15 ms 19284 KB Output is correct
4 Correct 13 ms 19284 KB Output is correct
5 Correct 13 ms 19236 KB Output is correct
6 Correct 12 ms 19284 KB Output is correct
7 Correct 12 ms 19280 KB Output is correct
8 Correct 12 ms 19312 KB Output is correct
9 Correct 15 ms 19276 KB Output is correct
10 Correct 14 ms 19316 KB Output is correct
11 Correct 13 ms 19408 KB Output is correct
12 Correct 12 ms 19296 KB Output is correct
13 Correct 17 ms 19240 KB Output is correct
14 Correct 2977 ms 19344 KB Output is correct
15 Correct 17 ms 19284 KB Output is correct
16 Correct 18 ms 19284 KB Output is correct
17 Correct 2665 ms 19328 KB Output is correct
18 Correct 16 ms 19412 KB Output is correct
19 Correct 20 ms 19324 KB Output is correct
20 Execution timed out 3058 ms 19284 KB Time limit exceeded
21 Halted 0 ms 0 KB -