oj.uz

답안 #648449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648449 2022-10-06T13:59:56 Z 406 함박 스테이크 (JOI20_hamburg) C++17
15 / 100
 3000 ms 31368 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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];
int cnt;

void rec();

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

inline 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)) {
                        cnt--;
                        used[i] = false;
                        change.push_back(i);
                }
        }
        if (change.empty())
                return;
        points.emplace_back(x, y);

        rec();

        for (auto cc: change) used[cc] = true, cnt++;
        points.pop_back();

}

void rec() {
        if (!cnt && 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 || 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;

                int mxD = 0;
                int mnU = 2 * n;
                for (int i = 0; i < n; i++) if (l[i] <= minR) {
                        mxD = max(mxD, d[i]);
                        mnU = min(mnU, u[i]);
                }
                add_point(minR, mxD);
                add_point(minR, mnU);
                mxD = 0;
                mnU = 2 * n;
                for (int i = 0; i < n; i++) if (r[i] >= maxL) {
                        mxD = max(mxD, d[i]);
                        mnU = min(mnU, u[i]);
                }

                add_point(maxL, mxD);
                add_point(maxL, mnU);

                int mxL = 0;
                int mnR = 2 * n;

                for (int i = 0; i < n; i++) if (u[i] >= maxD) {
                        mxL = max(mxL, l[i]);
                        mnR = min(mnR, r[i]);
                }
                add_point(mxL, maxD);
                add_point(mnR, maxD);

                mxL = 0;
                mnR = 2 * n;

                for (int i = 0; i < n; i++) if (d[i] <= minU) {
                        mxL = max(mxL, l[i]);
                        mnR = min(mnR, r[i]);
                }

                add_point(mxL, minU);
                add_point(mnR, minU);

                for (int i = 0; i < n; i++) if (l[i] <= minR)
                        op[d[i]].push_back(i), cl[u[i]].push_back(i);
                bool prv_open = false;
                for (int h = 0; h < Y.size(); h++) {
                        for (auto u: op[h]) {
                                used[u] = false;
                                cnt--;
                                prv_open = true;
                        }
                        if (cl[h].size() && prv_open) {
                                rec();
                                prv_open = false;
                        }
                        for (auto v: cl[h]) {
                                used[v] = true;
                                cnt++;
                        }
                }
        }
}

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;
        cnt = n;

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

Compilation message

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

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 11 ms 19156 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct

Subtask #2
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19124 KB Output is correct
2 Correct 11 ms 19156 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19228 KB Output is correct
3 Correct 12 ms 19200 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 11 ms 19204 KB Output is correct
6 Correct 11 ms 19116 KB Output is correct
7 Correct 12 ms 19228 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 13 ms 19176 KB Output is correct
10 Correct 13 ms 19156 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 12 ms 19152 KB Output is correct

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19096 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 11 ms 19216 KB Output is correct
5 Correct 11 ms 19156 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 11 ms 19228 KB Output is correct
9 Correct 12 ms 19168 KB Output is correct
10 Correct 13 ms 19156 KB Output is correct
11 Correct 14 ms 19156 KB Output is correct
12 Correct 11 ms 19156 KB Output is correct
13 Correct 17 ms 19204 KB Output is correct
14 Execution timed out 3076 ms 31368 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 11 ms 19156 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 271 ms 26532 KB Output is correct
6 Correct 266 ms 26500 KB Output is correct
7 Correct 269 ms 26604 KB Output is correct
8 Correct 276 ms 26572 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19124 KB Output is correct
2 Correct 11 ms 19156 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 270 ms 26528 KB Output is correct
6 Correct 273 ms 26936 KB Output is correct
7 Correct 267 ms 26700 KB Output is correct
8 Correct 280 ms 26668 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19228 KB Output is correct
3 Correct 12 ms 19200 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 11 ms 19204 KB Output is correct
6 Correct 11 ms 19116 KB Output is correct
7 Correct 12 ms 19228 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 13 ms 19176 KB Output is correct
10 Correct 13 ms 19156 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 12 ms 19152 KB Output is correct
13 Correct 277 ms 26572 KB Output is correct
14 Correct 280 ms 26352 KB Output is correct
15 Correct 275 ms 26536 KB Output is correct
16 Correct 271 ms 26556 KB Output is correct
17 Correct 268 ms 26404 KB Output is correct
18 Correct 272 ms 26532 KB Output is correct
19 Correct 273 ms 26444 KB Output is correct
20 Correct 291 ms 26328 KB Output is correct
21 Correct 375 ms 26704 KB Output is correct
22 Correct 313 ms 26444 KB Output is correct
23 Correct 304 ms 26580 KB Output is correct
24 Correct 303 ms 26580 KB Output is correct

Subtask #8
0 / 79.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19096 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 11 ms 19216 KB Output is correct
5 Correct 11 ms 19156 KB Output is correct
6 Correct 11 ms 19104 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 11 ms 19228 KB Output is correct
9 Correct 12 ms 19168 KB Output is correct
10 Correct 13 ms 19156 KB Output is correct
11 Correct 14 ms 19156 KB Output is correct
12 Correct 11 ms 19156 KB Output is correct
13 Correct 17 ms 19204 KB Output is correct
14 Execution timed out 3076 ms 31368 KB Time limit exceeded
15 Halted 0 ms 0 KB -