Submission #1134012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134012		OI_Account	Hamburg Steak (JOI20_hamburg)	C++20	3 / 100	3055 ms	466692 KiB

hamburg

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

#define X first
#define Y second

typedef pair<int, int> point;
typedef pair<point, point> rect;

const int N = 200'000;

int n, k, mark[N + 10];
point a[N + 10], b[N + 10];
rect r[N + 10];
vector<int> adj[N + 10];

void readInput() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].X >> a[i].Y;
        cin >> b[i].X >> b[i].Y;
        r[i] = {{a[i].X, b[i].X}, {a[i].Y, b[i].Y}};
    }
}

point common(point a, point b) {
    return {max(a.first, b.first), min(a.second, b.second)};
}

rect common(rect a, rect b) {
    return {common(a.first, b.first), common(a.second, b.second)};
}

point getPoint(rect res) {
    return {res.X.X, res.Y.X};
}

void solveSub1() {
    rect res = r[1];
    for (int i = 2; i <= n; i++)
        res = common(res, r[i]);
    cout << res.X.X << ' ' << res.Y.X << flush;
}

bool notEmp(rect now) {
    return (now.X.X <= now.X.Y && now.Y.X <= now.Y.Y);
}

bool good(rect x, rect y) {
    return notEmp(common(x, y));
}

vector<rect> merg(vector<rect> &x, vector<rect> &y, vector<rect> &vec) {
    vector<rect> tmp = x, all;
    for (auto p: y)
        tmp.push_back(p);
    for (int mask = 1; mask < (1 << (int) tmp.size()); mask++) {
        rect now;
        bool t = false;
        for (int j = 0; j < tmp.size(); j++)
            if ((mask & (1 << j))) {
                now = (t? common(now, tmp[j]): tmp[j]);
                t = true;
            }
        if (notEmp(now))
            all.push_back(now);
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    //cout << all.size() << endl;
    if (all.size() <= 2)
        return all;
    int resMask = -1, len = N + N;
    for (int i = 0; i < all.size(); i++)
        for (int j = 0; j < all.size(); j++) {
            bool ok = true;
            for (auto r: vec)
                if (!(common(all[i], r) == all[i] || common(all[j], r) == all[j])) {
                    ok = false;
                    break;
                }
            if (ok) {
                vector<rect> res;
                if (i != j)
                    res = {all[i], all[j]};
                else
                    res = {all[i]};
                return res;
            }
        }
    return {all[0], all[1]};
}

void write(vector<rect> vec) {
        for (auto r: vec)
        cout << "[" << r.X.X << ' ' << r.X.Y << ' ' << r.Y.X << ' ' << r.Y.Y << "] ";
    cout << endl;
}

vector<rect> solveSub2(vector<rect> vec) {
    //cout << "vec " << vec.size() << endl;
    if (vec.size() == 1)
        return vector<rect>{vec[0]};

    vector<rect> l, r;
    int mid = (int) vec.size() / 2;
    for (int i = 0; i < mid; i++)
        l.push_back(vec[i]);
    for (int i = mid; i < vec.size(); i++)
        r.push_back(vec[i]);

    vector<rect> lft = solveSub2(l), rght = solveSub2(r);
    //cout << "this "; write(vec);

    vector<rect> res = merg(lft, rght, vec);
    //cout << "res "; write(res);

    return res;
}

void dfs(int u, int h = 0) {
    mark[u] = h % 2 + 1;
    for (auto v: adj[u])
        if (!mark[v])
            dfs(v, h + 1);
}

void writeP(point p) {
    cout << p.X << ' ' << p.Y << '\n';
}

void solveSub2() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (j != i && good(r[i], r[j]) == false)
                adj[i].push_back(j);
    for (int i = 1; i <= n; i++)
        if (!mark[i])
            dfs(i);
    bool t[3] = {0};
    rect res[3];
    for (int i = 1; i <= n; i++) {
        res[mark[i]] = (t[mark[i]]? common(res[mark[i]], r[i]): r[i]);
        t[mark[i]] = true;
    }
    writeP(getPoint(res[2]));
    writeP(getPoint(res[1]));
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    if (k == 1)
        solveSub1();
    else if (k == 2)
        solveSub2();
    return 0;
}

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