oj.uz

Submission #648516

# Submission time Handle Problem Language Result Execution time Memory
648516 2022-10-06T18:58:05 Z 406 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 602 ms 749964 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;

                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;

                        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 169532 KB Output is correct
2 Correct 89 ms 169680 KB Output is correct
3 Correct 85 ms 169512 KB Output is correct
4 Correct 78 ms 169636 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 169584 KB Output is correct
2 Correct 83 ms 169620 KB Output is correct
3 Correct 85 ms 169548 KB Output is correct
4 Correct 86 ms 169732 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169548 KB Output is correct
2 Correct 82 ms 169556 KB Output is correct
3 Correct 83 ms 169576 KB Output is correct
4 Correct 84 ms 169596 KB Output is correct
5 Correct 82 ms 169640 KB Output is correct
6 Correct 82 ms 169608 KB Output is correct
7 Correct 83 ms 169664 KB Output is correct
8 Correct 88 ms 169580 KB Output is correct
9 Correct 81 ms 169568 KB Output is correct
10 Correct 91 ms 169652 KB Output is correct
11 Correct 82 ms 169576 KB Output is correct
12 Correct 83 ms 169528 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169596 KB Output is correct
2 Correct 79 ms 169648 KB Output is correct
3 Correct 82 ms 169624 KB Output is correct
4 Correct 82 ms 169576 KB Output is correct
5 Correct 79 ms 169640 KB Output is correct
6 Correct 90 ms 169652 KB Output is correct
7 Correct 81 ms 169576 KB Output is correct
8 Correct 80 ms 169548 KB Output is correct
9 Correct 83 ms 169548 KB Output is correct
10 Correct 87 ms 169624 KB Output is correct
11 Correct 88 ms 169576 KB Output is correct
12 Correct 80 ms 169612 KB Output is correct
13 Correct 90 ms 169548 KB Output is correct
14 Runtime error 602 ms 749964 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 169532 KB Output is correct
2 Correct 89 ms 169680 KB Output is correct
3 Correct 85 ms 169512 KB Output is correct
4 Correct 78 ms 169636 KB Output is correct
5 Correct 409 ms 178284 KB Output is correct
6 Correct 366 ms 178288 KB Output is correct
7 Correct 353 ms 178320 KB Output is correct
8 Correct 365 ms 178300 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 169584 KB Output is correct
2 Correct 83 ms 169620 KB Output is correct
3 Correct 85 ms 169548 KB Output is correct
4 Correct 86 ms 169732 KB Output is correct
5 Correct 362 ms 178076 KB Output is correct
6 Correct 349 ms 178172 KB Output is correct
7 Correct 378 ms 178052 KB Output is correct
8 Correct 388 ms 177984 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169548 KB Output is correct
2 Correct 82 ms 169556 KB Output is correct
3 Correct 83 ms 169576 KB Output is correct
4 Correct 84 ms 169596 KB Output is correct
5 Correct 82 ms 169640 KB Output is correct
6 Correct 82 ms 169608 KB Output is correct
7 Correct 83 ms 169664 KB Output is correct
8 Correct 88 ms 169580 KB Output is correct
9 Correct 81 ms 169568 KB Output is correct
10 Correct 91 ms 169652 KB Output is correct
11 Correct 82 ms 169576 KB Output is correct
12 Correct 83 ms 169528 KB Output is correct
13 Correct 384 ms 178052 KB Output is correct
14 Correct 374 ms 178012 KB Output is correct
15 Correct 356 ms 178156 KB Output is correct
16 Correct 361 ms 178064 KB Output is correct
17 Correct 375 ms 177992 KB Output is correct
18 Correct 362 ms 178240 KB Output is correct
19 Correct 387 ms 178064 KB Output is correct
20 Correct 386 ms 178056 KB Output is correct
21 Correct 484 ms 178136 KB Output is correct
22 Correct 431 ms 178036 KB Output is correct
23 Correct 414 ms 177996 KB Output is correct
24 Correct 424 ms 178028 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169596 KB Output is correct
2 Correct 79 ms 169648 KB Output is correct
3 Correct 82 ms 169624 KB Output is correct
4 Correct 82 ms 169576 KB Output is correct
5 Correct 79 ms 169640 KB Output is correct
6 Correct 90 ms 169652 KB Output is correct
7 Correct 81 ms 169576 KB Output is correct
8 Correct 80 ms 169548 KB Output is correct
9 Correct 83 ms 169548 KB Output is correct
10 Correct 87 ms 169624 KB Output is correct
11 Correct 88 ms 169576 KB Output is correct
12 Correct 80 ms 169612 KB Output is correct
13 Correct 90 ms 169548 KB Output is correct
14 Runtime error 602 ms 749964 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -