oj.uz

Submission #648513

# Submission time Handle Problem Language Result Execution time Memory
648513 2022-10-06T18:55:25 Z 406 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 665 ms 740596 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();

}
const int V = 16 * N;
vector<int> adj[V], adj_t[V];
bitset<V> mark, ass;
vector<int> order;
int comp[V];

void dfs1(int v) {
        mark[v] = true;
        for (auto u: adj[v]) if (!mark[u])
                dfs1(u);
        order.push_back(v);
}

void dfs2(int v, int cl) {
        comp[v] = cl;
        for (auto u: adj_t[v]) {
                if (comp[u] == -1)
                        dfs2(u, cl);
        }
}
void solve_2SAT() {
        for (int i = 0; i < V; i++) if (!mark[i])
                dfs1(i);
        fill(comp, comp + V, -1);

        for (int i = 0, j = 0; i < V; i++) {
                int v = order[V - i - 1];
                if (comp[v] == -1)
                        dfs2(v, j++);
        }

        for (int i = 0; i < V; i += 2)
                ass[i / 2] = comp[i] > comp[i + 1];
}

void add_disjunction(int a, bool na, int b, bool nb) {
        a = 2 * a ^ na;
        b = 2 * b ^ nb;
        int neg_a = a ^ 1;
        int neg_b = b ^ 1;
        adj[neg_a].push_back(b);
        adj[neg_b].push_back(a);

        adj_t[b].push_back(neg_a);
        adj_t[a].push_back(neg_b);
}
void add_two(int a, int b, int c, int d) {
        a--, c--;
        add_disjunction(a, 1, c, 1);
        add_disjunction(a, 1, d, 0);
        add_disjunction(b, 1, c, 1);
        add_disjunction(b, 1, d, 0);
}

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

                for (int i = 0; i < n; i++) {
                        l[i] = max(l[i], minR);
                        r[i] = min(r[i], maxL);
                        d[i] = max(d[i], minU);
                        u[i] = min(u[i], maxD);
                        int q = (l[i] == minR) + (r[i] == maxL) + (d[i] == minU) + (u[i] == maxD);
                        if (q >= 3)
                                continue;
                        assert(q == 1 || q == 2);

                        if (q == 1) {
                                if (l[i] == minR)
                                        add_disjunction(d[i] - 1, true, d[i] - 1, true),
                                        add_disjunction(u[i], false, u[i], false);
                                else if (r[i] == maxL)
                                        add_disjunction(2 * M + d[i] - 1, true, 2 * M + d[i] - 1, true),
                                        add_disjunction(2 * M + u[i], false, 2 * M + u[i], false);
                                else if (d[i] == minU)
                                        add_disjunction(3 * M + l[i] - 1, true, 3 * M + l[i] - 1, true), 
                                        add_disjunction(3 * M + r[i], false, 3 * M + r[i], false);
                                else  //u[i] == maxD
                                        add_disjunction(M + l[i] - 1, true, M + l[i] - 1, true),
                                        add_disjunction(M + r[i], false, M + r[i], false);
                        }
                        else {
                                if (l[i] == minR && r[i] == maxL)
                                        add_two(d[i], u[i], 2 * M + d[i], 2 * M + u[i]);
                                else if (l[i] == minR && d[i] == minU)
                                        add_two(d[i], u[i], 3 * M + l[i], 3 * M + r[i]);
                                else if (l[i] == minR && u[i] == maxD)
                                        add_two(d[i], u[i], M + l[i], M + r[i]);
                                else if (r[i] == maxL && d[i] == minU)
                                        add_two(2 * M + d[i], 2 * M + u[i], 3 * M + l[i], 3 * M + r[i]);
                                else if (r[i] == maxL && u[i] == maxD)
                                        add_two(2 * M + d[i], 2 * M + u[i], M + l[i], M + r[i]);
                                else if (d[i] == minU && u[i] == maxD) 
                                        add_two(3 * M + l[i], 3 * M + r[i], M + l[i], M + r[i]);
                        }
                }
                //init edges
                for (int j = 0; j < 4; j++)
                        for (int i = j * M; i < (j + 1) * M - 1; i++)
                                add_disjunction(i, true, i + 1, false);
                solve_2SAT();

                for (int i = 0; i < M; i++)
                        if (ass[i])
                                add_point(minR, i);

        }
}


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

        cin >> n >> k;
        X.reserve(2 * n), Y.reserve(2 * n);
        X.push_back(-1), Y.push_back(-1);
        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:95: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]
   95 |         if (!cnt && points.size() <= k) {
      |                     ~~~~~~~~~~~~~~^~~~
hamburg.cpp:102: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]
  102 |         if (points.size() >= k)
      |             ~~~~~~~~~~~~~~^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169576 KB Output is correct
2 Correct 81 ms 169576 KB Output is correct
3 Correct 89 ms 169596 KB Output is correct
4 Correct 90 ms 169568 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 169556 KB Output is correct
2 Correct 95 ms 169652 KB Output is correct
3 Correct 80 ms 169580 KB Output is correct
4 Correct 84 ms 169700 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 169840 KB Output is correct
2 Correct 92 ms 169652 KB Output is correct
3 Correct 85 ms 169644 KB Output is correct
4 Correct 82 ms 169640 KB Output is correct
5 Correct 87 ms 169600 KB Output is correct
6 Correct 87 ms 169644 KB Output is correct
7 Correct 83 ms 169576 KB Output is correct
8 Correct 85 ms 169580 KB Output is correct
9 Correct 86 ms 169604 KB Output is correct
10 Correct 91 ms 169580 KB Output is correct
11 Correct 81 ms 169548 KB Output is correct
12 Correct 88 ms 169568 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 169576 KB Output is correct
2 Correct 84 ms 169676 KB Output is correct
3 Correct 81 ms 169528 KB Output is correct
4 Correct 79 ms 169540 KB Output is correct
5 Correct 84 ms 169548 KB Output is correct
6 Correct 94 ms 169552 KB Output is correct
7 Correct 94 ms 169652 KB Output is correct
8 Correct 84 ms 169752 KB Output is correct
9 Correct 94 ms 169564 KB Output is correct
10 Correct 84 ms 169544 KB Output is correct
11 Correct 82 ms 169552 KB Output is correct
12 Correct 81 ms 169616 KB Output is correct
13 Correct 83 ms 169624 KB Output is correct
14 Runtime error 665 ms 740596 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169576 KB Output is correct
2 Correct 81 ms 169576 KB Output is correct
3 Correct 89 ms 169596 KB Output is correct
4 Correct 90 ms 169568 KB Output is correct
5 Correct 428 ms 182260 KB Output is correct
6 Correct 392 ms 182260 KB Output is correct
7 Correct 385 ms 182260 KB Output is correct
8 Correct 389 ms 182256 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 169556 KB Output is correct
2 Correct 95 ms 169652 KB Output is correct
3 Correct 80 ms 169580 KB Output is correct
4 Correct 84 ms 169700 KB Output is correct
5 Correct 390 ms 182088 KB Output is correct
6 Correct 401 ms 182192 KB Output is correct
7 Correct 386 ms 181756 KB Output is correct
8 Correct 403 ms 181756 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 169840 KB Output is correct
2 Correct 92 ms 169652 KB Output is correct
3 Correct 85 ms 169644 KB Output is correct
4 Correct 82 ms 169640 KB Output is correct
5 Correct 87 ms 169600 KB Output is correct
6 Correct 87 ms 169644 KB Output is correct
7 Correct 83 ms 169576 KB Output is correct
8 Correct 85 ms 169580 KB Output is correct
9 Correct 86 ms 169604 KB Output is correct
10 Correct 91 ms 169580 KB Output is correct
11 Correct 81 ms 169548 KB Output is correct
12 Correct 88 ms 169568 KB Output is correct
13 Correct 396 ms 181244 KB Output is correct
14 Correct 410 ms 181260 KB Output is correct
15 Correct 393 ms 181264 KB Output is correct
16 Correct 386 ms 181232 KB Output is correct
17 Correct 383 ms 181224 KB Output is correct
18 Correct 381 ms 181360 KB Output is correct
19 Correct 433 ms 181236 KB Output is correct
20 Correct 412 ms 181256 KB Output is correct
21 Correct 559 ms 181764 KB Output is correct
22 Correct 439 ms 181796 KB Output is correct
23 Correct 404 ms 181724 KB Output is correct
24 Correct 408 ms 181692 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 169576 KB Output is correct
2 Correct 84 ms 169676 KB Output is correct
3 Correct 81 ms 169528 KB Output is correct
4 Correct 79 ms 169540 KB Output is correct
5 Correct 84 ms 169548 KB Output is correct
6 Correct 94 ms 169552 KB Output is correct
7 Correct 94 ms 169652 KB Output is correct
8 Correct 84 ms 169752 KB Output is correct
9 Correct 94 ms 169564 KB Output is correct
10 Correct 84 ms 169544 KB Output is correct
11 Correct 82 ms 169552 KB Output is correct
12 Correct 81 ms 169616 KB Output is correct
13 Correct 83 ms 169624 KB Output is correct
14 Runtime error 665 ms 740596 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -