oj.uz

Submission #648562

# Submission time Handle Problem Language Result Execution time Memory
648562 2022-10-07T03:06:49 Z 406 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 520 ms 402420 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;
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 = 2 * 4 * M;
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() {
        mark = 0;
        for (int i = 0; i < V; i++) if (!mark[i])
                dfs1(i);
        fill(comp, comp + V, -1);

        assert(order.size() == V);

        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) {
        assert(a > 0 && c > 0);
        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;
                        assert(q);

                        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();
                cout << "SOLVED 2SAT\n";
                exit(0);

                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:99: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]
   99 |         if (!cnt && points.size() <= k) {
      |                     ~~~~~~~~~~~~~~^~~~
hamburg.cpp:106: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]
  106 |         if (points.size() >= k)
      |             ~~~~~~~~~~~~~~^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 150732 KB Output is correct
2 Correct 79 ms 150712 KB Output is correct
3 Correct 81 ms 150732 KB Output is correct
4 Correct 70 ms 150796 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 150784 KB Output is correct
2 Correct 72 ms 150696 KB Output is correct
3 Correct 79 ms 150820 KB Output is correct
4 Correct 91 ms 150688 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 150760 KB Output is correct
2 Correct 73 ms 150720 KB Output is correct
3 Correct 71 ms 150740 KB Output is correct
4 Correct 84 ms 150768 KB Output is correct
5 Correct 90 ms 150696 KB Output is correct
6 Correct 70 ms 150724 KB Output is correct
7 Correct 72 ms 150712 KB Output is correct
8 Correct 71 ms 150732 KB Output is correct
9 Correct 78 ms 150672 KB Output is correct
10 Correct 81 ms 150776 KB Output is correct
11 Correct 71 ms 150668 KB Output is correct
12 Correct 76 ms 150800 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 150688 KB Output is correct
2 Correct 93 ms 150852 KB Output is correct
3 Correct 93 ms 150676 KB Output is correct
4 Correct 85 ms 150776 KB Output is correct
5 Correct 88 ms 150772 KB Output is correct
6 Correct 94 ms 150696 KB Output is correct
7 Correct 91 ms 150668 KB Output is correct
8 Correct 95 ms 150696 KB Output is correct
9 Correct 91 ms 150716 KB Output is correct
10 Correct 81 ms 150756 KB Output is correct
11 Correct 103 ms 150872 KB Output is correct
12 Correct 99 ms 150712 KB Output is correct
13 Correct 74 ms 150772 KB Output is correct
14 Incorrect 520 ms 402420 KB Expected integer, but "SOLVED" found
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 150732 KB Output is correct
2 Correct 79 ms 150712 KB Output is correct
3 Correct 81 ms 150732 KB Output is correct
4 Correct 70 ms 150796 KB Output is correct
5 Correct 341 ms 158728 KB Output is correct
6 Correct 355 ms 158856 KB Output is correct
7 Correct 333 ms 158768 KB Output is correct
8 Correct 332 ms 158732 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 150784 KB Output is correct
2 Correct 72 ms 150696 KB Output is correct
3 Correct 79 ms 150820 KB Output is correct
4 Correct 91 ms 150688 KB Output is correct
5 Correct 377 ms 158508 KB Output is correct
6 Correct 380 ms 158600 KB Output is correct
7 Correct 328 ms 158560 KB Output is correct
8 Correct 367 ms 158412 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 150760 KB Output is correct
2 Correct 73 ms 150720 KB Output is correct
3 Correct 71 ms 150740 KB Output is correct
4 Correct 84 ms 150768 KB Output is correct
5 Correct 90 ms 150696 KB Output is correct
6 Correct 70 ms 150724 KB Output is correct
7 Correct 72 ms 150712 KB Output is correct
8 Correct 71 ms 150732 KB Output is correct
9 Correct 78 ms 150672 KB Output is correct
10 Correct 81 ms 150776 KB Output is correct
11 Correct 71 ms 150668 KB Output is correct
12 Correct 76 ms 150800 KB Output is correct
13 Correct 330 ms 158576 KB Output is correct
14 Correct 353 ms 158428 KB Output is correct
15 Correct 342 ms 158508 KB Output is correct
16 Correct 331 ms 158532 KB Output is correct
17 Correct 344 ms 158412 KB Output is correct
18 Correct 373 ms 158600 KB Output is correct
19 Correct 353 ms 158488 KB Output is correct
20 Correct 369 ms 158412 KB Output is correct
21 Correct 474 ms 158572 KB Output is correct
22 Correct 386 ms 158412 KB Output is correct
23 Correct 384 ms 158492 KB Output is correct
24 Correct 358 ms 158556 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 150688 KB Output is correct
2 Correct 93 ms 150852 KB Output is correct
3 Correct 93 ms 150676 KB Output is correct
4 Correct 85 ms 150776 KB Output is correct
5 Correct 88 ms 150772 KB Output is correct
6 Correct 94 ms 150696 KB Output is correct
7 Correct 91 ms 150668 KB Output is correct
8 Correct 95 ms 150696 KB Output is correct
9 Correct 91 ms 150716 KB Output is correct
10 Correct 81 ms 150756 KB Output is correct
11 Correct 103 ms 150872 KB Output is correct
12 Correct 99 ms 150712 KB Output is correct
13 Correct 74 ms 150772 KB Output is correct
14 Incorrect 520 ms 402420 KB Expected integer, but "SOLVED" found
15 Halted 0 ms 0 KB -