Submission #384656

#	Time	Username	Problem	Language	Result	Execution time	Memory
384656		timmyfeng	Hamburg Steak (JOI20_hamburg)	C++17	Compilation error	0 ms	0 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

const int N = 200000, X = 1000000000;

vector<array<int, 2>> ans;
array<int, 4> rect[N];
bool tested[N];
int n, k;

vector<int> adj[N], jda[N], order;
int color[N], s, m;
bool visited[N];

void add_expr(int u, int v) {
    adj[u ^ 1].push_back(v);
    adj[v ^ 1].push_back(u);
    jda[u].push_back(v ^ 1);
    jda[v].push_back(u ^ 1);
}

struct side {
    map<int, int> map, prefix, suffix;

    void add(int x) {
        if (map.count(x) == 0) {
            suffix[x] = m + 4;
            prefix[x] = m + 2;
            map[x] = m;
            m += 6;
        }
    }

    int less(int x) {
        add(x);
        return prefix[x];
    }

    int greater(int x) {
        add(x);
        return suffix[x];
    }

    void init() {
        vector<pair<int, int>> pairs(map.begin(), map.end());
        for (int i = 1; i < (int) pairs.size(); ++i) {
            int x = pairs[i - 1].first, y = pairs[i].first;
            add_expr(prefix[x] ^ 1, suffix[y] ^ 1);
            add_expr(prefix[x] ^ 1, map[y] ^ 1);
            add_expr(map[x] ^ 1, suffix[y] ^ 1);
        }
    }

    int find() {
        for (auto [x, y] : map) {
            if (color[y] > color[y + 1]) {
                return x;
            }
        }
        return -1;
    }
};

array<int, 4> bounds() {
    int x1 = X, x2 = 0, y1 = X, y2 = 0;
    for (int i = 0; i < n; ++i) {
        auto [l, d, r, u] = rect[i];
        if (!tested[i]) {
            x1 = min(x1, r);
            x2 = max(x2, l);
            y1 = min(y1, u);
            y2 = max(y2, d);
        }
    }
    return {x1, x2, y1, y2};
}

void solve() {
    if (count(tested, tested + n, false) == 0) {
        while ((int) ans.size() < k) {
            ans.push_back(ans.back());
        }
        for (auto [x, y] : ans) {
            cout << x << " " << y << "\n";
        }
        exit(0);
    } else if ((int) ans.size() == k) {
        return;
    }

    auto [x1, x2, y1, y2] = bounds();

    for (auto x : {x1, x2}) {
        for (auto y : {y1, y2}) {
            ans.push_back({x, y});
            vector<int> undo;
            for (int i = 0; i < n; ++i) {
                auto [l, d, r, u] = rect[i];
                if (!tested[i] && l <= x && x <= r && d <= y && y <= u) {
                    undo.push_back(i);
                    tested[i] = true;
                }
            }

            solve();

            for (auto i : undo) {
                tested[i] = false;
            }
            ans.pop_back();
        }
    }
}

void dfs_order(int u) {
    visited[u] = true;
    for (auto c : adj[u]) {
        if (!visited[c]) {
            dfs_order(c);
        }
    }
    order.push_back(u);
}

void dfs_color(int u, int x) {
    color[u] = x;
    for (auto c : jda[u]) {
        if (color[c] != 0) {
            dfs_color(c, x);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        for (auto &j : rect[i]) {
            cin >> j;
        }
    }

    solve();

    auto [x1, x2, y1, y2] = bounds();
    side left, down, right, up;

    for (int i = 0; i < n; ++i) {
        auto [l, d, r, u] = rect[i];
        if (!(l <= x1 && x2 <= r) && !(d <= y1 && y2 <= u)) {
            if (l <= x1 && d <= y1) {
                add_expr(left.less(u), down.less(r));
            } else if (l <= x1 && u >= y2) {
                add_expr(left.greater(d), up.less(r));
            } else if (r >= x2 && d <= y1) {
                add_expr(right.less(u), down.greater(l));
            } else if (r >= x2 && u >= y2) {
                add_expr(right.greater(d), up.greater(l));
            } else if (l <= x1) {
                add_expr(left.greater(d), left.greater(d));
                add_expr(left.less(u), left.less(u));
            } else if (r >= x2) {
                add_expr(right.greater(d), right.greater(d));
                add_expr(right.less(u), right.less(u));
            } else if (d <= y1) {
                add_expr(down.greater(l), down.greater(l));
                add_expr(down.less(r), down.less(r));
            } else if (u >= y2) {
                add_expr(up.greater(l), up.greater(l));
                add_expr(up.less(r), up.less(r));
            }
        }
    }

    left.init();
    down.init();
    right.init();
    up.init();

    for (int i = 0; i < m; ++i) {
        if (!visited[i]) {
            dfs_order(i);
        }
    }

    reverse(order.begin(), order.end());
    for (auto i : order) {
        if (color[i] == 0) {
            dfs_color(i, ++s);
        }
    }

    cout << x1 << " " << left.find() << "\n";
    cout << down.find() << " " << y1 << "\n";
    cout << x2 << " " << right.find() << "\n";
    cout << up.find() << " " << y2 << "\n";
}

Compilation message (stderr)

hamburg.cpp:23:19: error: declaration of 'std::map<int, int> side::map' changes meaning of 'map' [-fpermissive]
   23 |     map<int, int> map, prefix, suffix;
      |                   ^~~
In file included from /usr/include/c++/9/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from hamburg.cpp:1:
/usr/include/c++/9/bits/stl_map.h:100:11: note: 'map' declared here as 'class std::map<int, int>'
  100 |     class map
      |           ^~~