oj.uz

Submission #648154

# Submission time Handle Problem Language Result Execution time Memory
648154 2022-10-05T14:25:56 Z 406 Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 3000 ms 40464 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++) {
                if (p.size() && p.back() == (h - 1))
                        p.back()++;
                else if (op[h].size())
                        p.push_back(h);
                if (cl[h].size())
                        p.push_back(-1);
        }

        /*
        sort(p.begin(), p.end());
        p.resize(unique(p.begin(), p.end()) - p.begin());
        */

        for (auto h: p) {
                if (h == -1) 
                        continue;
                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 19284 KB Output is correct
2 Correct 15 ms 19312 KB Output is correct
3 Correct 16 ms 19284 KB Output is correct
4 Correct 12 ms 19284 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19392 KB Output is correct
2 Correct 44 ms 19364 KB Output is correct
3 Correct 14 ms 19304 KB Output is correct
4 Correct 17 ms 19344 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19284 KB Output is correct
2 Correct 13 ms 19328 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 15 ms 19372 KB Output is correct
5 Correct 12 ms 19364 KB Output is correct
6 Correct 13 ms 19372 KB Output is correct
7 Correct 14 ms 19356 KB Output is correct
8 Correct 33 ms 19336 KB Output is correct
9 Correct 1797 ms 19384 KB Output is correct
10 Correct 1852 ms 19380 KB Output is correct
11 Correct 25 ms 19372 KB Output is correct
12 Correct 343 ms 19404 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19404 KB Output is correct
2 Correct 13 ms 19332 KB Output is correct
3 Correct 12 ms 19292 KB Output is correct
4 Correct 13 ms 19420 KB Output is correct
5 Correct 14 ms 19384 KB Output is correct
6 Correct 17 ms 19360 KB Output is correct
7 Correct 13 ms 19412 KB Output is correct
8 Correct 16 ms 19284 KB Output is correct
9 Correct 119 ms 19380 KB Output is correct
10 Correct 84 ms 19276 KB Output is correct
11 Correct 159 ms 19364 KB Output is correct
12 Correct 12 ms 19284 KB Output is correct
13 Execution timed out 3077 ms 19412 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19284 KB Output is correct
2 Correct 15 ms 19312 KB Output is correct
3 Correct 16 ms 19284 KB Output is correct
4 Correct 12 ms 19284 KB Output is correct
5 Correct 352 ms 40284 KB Output is correct
6 Correct 381 ms 40280 KB Output is correct
7 Correct 375 ms 40244 KB Output is correct
8 Correct 374 ms 40256 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19392 KB Output is correct
2 Correct 44 ms 19364 KB Output is correct
3 Correct 14 ms 19304 KB Output is correct
4 Correct 17 ms 19344 KB Output is correct
5 Correct 375 ms 39956 KB Output is correct
6 Execution timed out 3070 ms 39744 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19284 KB Output is correct
2 Correct 13 ms 19328 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 15 ms 19372 KB Output is correct
5 Correct 12 ms 19364 KB Output is correct
6 Correct 13 ms 19372 KB Output is correct
7 Correct 14 ms 19356 KB Output is correct
8 Correct 33 ms 19336 KB Output is correct
9 Correct 1797 ms 19384 KB Output is correct
10 Correct 1852 ms 19380 KB Output is correct
11 Correct 25 ms 19372 KB Output is correct
12 Correct 343 ms 19404 KB Output is correct
13 Correct 403 ms 39616 KB Output is correct
14 Correct 397 ms 40464 KB Output is correct
15 Correct 385 ms 39592 KB Output is correct
16 Correct 445 ms 40392 KB Output is correct
17 Correct 404 ms 39732 KB Output is correct
18 Correct 377 ms 40308 KB Output is correct
19 Correct 377 ms 39792 KB Output is correct
20 Execution timed out 3063 ms 38716 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19404 KB Output is correct
2 Correct 13 ms 19332 KB Output is correct
3 Correct 12 ms 19292 KB Output is correct
4 Correct 13 ms 19420 KB Output is correct
5 Correct 14 ms 19384 KB Output is correct
6 Correct 17 ms 19360 KB Output is correct
7 Correct 13 ms 19412 KB Output is correct
8 Correct 16 ms 19284 KB Output is correct
9 Correct 119 ms 19380 KB Output is correct
10 Correct 84 ms 19276 KB Output is correct
11 Correct 159 ms 19364 KB Output is correct
12 Correct 12 ms 19284 KB Output is correct
13 Execution timed out 3077 ms 19412 KB Time limit exceeded
14 Halted 0 ms 0 KB -