Submission #648565

#	Time	Username	Problem	Language	Result	Execution time	Memory
648565		406	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	2116 ms	422004 KiB

hamburg

#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;
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, 0, c, 1);
        add_disjunction(b, 0, 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, 1, d[i] - 1, 1),
                                        add_disjunction(u[i], 0, u[i], 0);
                                else if (r[i] == maxL)
                                        add_disjunction(2 * M + d[i] - 1, 1, 2 * M + d[i] - 1, 1),
                                        add_disjunction(2 * M + u[i], 0, 2 * M + u[i], 0);
                                else if (d[i] == minU)
                                        add_disjunction(3 * M + l[i] - 1, 1, 3 * M + l[i] - 1, 1), 
                                        add_disjunction(3 * M + r[i], 0, 3 * M + r[i], 0);
                                else  //u[i] == maxD
                                        add_disjunction(M + l[i] - 1, 1, M + l[i] - 1, 1),
                                        add_disjunction(M + r[i], 0, M + r[i], 0);
                        }
                        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);
                                break;
                        }
                cout << "IMPOSSIBLE\n";
                exit(0);
        }
}


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 (stderr)

hamburg.cpp: In function 'void rec()':
hamburg.cpp:96: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]
   96 |         if (!cnt && points.size() <= k) {
      |                     ~~~~~~~~~~~~~~^~~~
hamburg.cpp:103: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]
  103 |         if (points.size() >= k)
      |             ~~~~~~~~~~~~~~^~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79