oj.uz

Submission #648333

# Submission time Handle Problem Language Result Execution time Memory
648333 2022-10-06T07:31:48 Z 406 Hamburg Steak (JOI20_hamburg) C++17
9 / 100
 3000 ms 26876 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.count() == 0;
}

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 = used._Find_first(); i < n; i = used._Find_next(i)) {
                if (inter(i, x, y)) {
                        used[i] = false;
                        change.push_back(i);
                }
        }
        points.emplace_back(x, y);

        rec();

        for (auto cc: change) used[cc] = true;
        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 = used._Find_first(); i < n; i = used._Find_next(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++)
                used[i] = true;

        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 15 ms 19156 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 12 ms 19216 KB Output is correct
4 Correct 12 ms 19212 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19208 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 14 ms 19220 KB Output is correct
3 Correct 13 ms 19324 KB Output is correct
4 Correct 14 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 12 ms 19156 KB Output is correct
8 Correct 14 ms 19200 KB Output is correct
9 Correct 529 ms 19328 KB Output is correct
10 Correct 388 ms 19332 KB Output is correct
11 Correct 14 ms 19220 KB Output is correct
12 Correct 14 ms 19156 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 11 ms 19196 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 12 ms 19156 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Incorrect 1405 ms 19196 KB Expected integer, but "NO" found
10 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19156 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 12 ms 19216 KB Output is correct
4 Correct 12 ms 19212 KB Output is correct
5 Correct 290 ms 26572 KB Output is correct
6 Correct 276 ms 26528 KB Output is correct
7 Correct 310 ms 26444 KB Output is correct
8 Correct 280 ms 26444 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19208 KB Output is correct
5 Correct 330 ms 26640 KB Output is correct
6 Correct 286 ms 26876 KB Output is correct
7 Correct 303 ms 26612 KB Output is correct
8 Correct 300 ms 26624 KB Output is correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 14 ms 19220 KB Output is correct
3 Correct 13 ms 19324 KB Output is correct
4 Correct 14 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 12 ms 19156 KB Output is correct
8 Correct 14 ms 19200 KB Output is correct
9 Correct 529 ms 19328 KB Output is correct
10 Correct 388 ms 19332 KB Output is correct
11 Correct 14 ms 19220 KB Output is correct
12 Correct 14 ms 19156 KB Output is correct
13 Correct 270 ms 26572 KB Output is correct
14 Correct 298 ms 26316 KB Output is correct
15 Correct 305 ms 26604 KB Output is correct
16 Correct 278 ms 26460 KB Output is correct
17 Correct 321 ms 26448 KB Output is correct
18 Correct 274 ms 26524 KB Output is correct
19 Correct 286 ms 26444 KB Output is correct
20 Correct 281 ms 26416 KB Output is correct
21 Execution timed out 3071 ms 26248 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 11 ms 19196 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 12 ms 19156 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Incorrect 1405 ms 19196 KB Expected integer, but "NO" found
10 Halted 0 ms 0 KB -