Submission #1308170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308170		M_W_13	Hamburg Steak (JOI20_hamburg)	C++20	21 / 100	3094 ms	25384 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
int N, k;


struct prostokat {
    int l, d, r, u;
};

struct pkt {
    int x, y;
};

bool check(prostokat p, pkt pt) {
    if (pt.x < p.l || pt.x > p.r) return false;
    if (pt.y < p.d || pt.y > p.u) return false;
    return true;
}

bool spr(vector<pkt> jakie, vector<prostokat> &T) {
    int rozm = (int)T.size();
    rep(i, rozm) {
        bool czy = false;
        for (auto p: jakie) {
            if (check(T[i], p)) {
                czy = true;
                break;
            }
        }
        if (!czy) return false;
    }
    return true;
}

pair<bool, vector<pkt>> solve2(vector<prostokat> T) {
    int n = (int)T.size();
    int X1[n];
    int X2[n];
    int Y1[n];
    int Y2[n];
    int minix = 1e9 + 1;
    int maksx = 0;
    int miniy = 1e9 + 1;
    int maksy = 0;
    rep(i, n) {
        X1[i] = T[i].l;
        X2[i] = T[i].r;
        Y1[i] = T[i].d;
        Y2[i] = T[i].u;
        minix = min(minix, X2[i]);
        maksx = max(maksx, X1[i]);
        miniy = min(miniy, Y2[i]);
        maksy = max(maksy, Y1[i]);
    }
    int val = 1e9 + 1;
    vector<int> A;
    vector<int> B;
    A.pb(minix);
    A.pb(maksx);
    B.pb(miniy);
    B.pb(maksy);
    int szA = A.size();
    int szB = B.size();
    int r = szA * szB;
    int maks = 1 << r;
    vector<pkt> pom;
    for (auto a: A) {
        for (auto b: B) {
            pom.pb({a, b});
        }
    }
    for (auto p: pom) {
        if (spr({p}, T)) {
            return {true, {p}};
        }
    }
    int sz = pom.size();
    rep(i, sz) {
        for (int j = i + 1; j < sz; j++) {
            pkt a = pom[i];
            pkt b = pom[j];
            // cout << a.x << " " << a.y << " " << b.x << " " << b.y << " XD" << '\n';
            if (spr({a, b}, T)) {
                // cout << "TAKPLS" << '\n';
                return {true, {a, b}};
            }
        }
    }
    return {false, {}};
}

pair<bool, vector<pkt>> solve3(vector<prostokat> T) {
    int n = (int)T.size();
    int minix = 1e9 + 1;
    int maksx = 0;
    int miniy = 1e9 + 1;
    int maksy = 0;
    rep(i, n) {
        minix = min(minix, T[i].r);
        maksx = max(maksx, T[i].l);
        miniy = min(miniy, T[i].u);
        maksy = max(maksy, T[i].d);
    }
    vector<int> A;
    vector<int> B;
    A.pb(minix);
    A.pb(maksx);
    B.pb(miniy);
    B.pb(maksy);
    for (auto a: A) {
        for (auto b: B) {
            vector<prostokat> vec;
            // cout << "a = " << a << " b = " << b << '\n';
            for (auto p: T) {
                if (!check(p, {a, b})) {
                    // cout << p.l << " " << p.r << " " << p.d << " " << p.u << '\n';
                    vec.pb(p);
                }
            }
            pair<bool, vector<pkt>> para = solve2(vec);
            if (para.st) {
                vector<pkt> ans;
                ans.pb({a, b});
                int sz = (para.nd).size();
                if (sz < 2) {
                    ans.pb({a, b});
                }
                for (auto p: para.nd) {
                    ans.pb(p);
                }
                return {true, ans};
            }
        }
    }
    return {false, {}};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> k;
    vector<prostokat> T;
    T.resize(N);
    int minix = 1e9 + 1;
    int maksx = 0;
    int miniy = 1e9 + 1;
    int maksy = 0;
    vector<int> A2;
    vector<int> B2;
    rep(i, N) {
        cin >> T[i].l >> T[i].d >> T[i].r >> T[i].u;
        minix = min(minix, T[i].r);
        maksx = max(maksx, T[i].l);
        miniy = min(miniy, T[i].u);
        maksy = max(maksy, T[i].d);
        A2.pb(T[i].l);
        A2.pb(T[i].r);
        B2.pb(T[i].d);
        B2.pb(T[i].u);
    }
    vector<int> A;
    vector<int> B;
    A.pb(minix);
    A.pb(maksx);
    B.pb(miniy);
    B.pb(maksy);
    pair<bool, vector<pkt>> para;
    para = solve2(T);
    if (!para.st) {
        para = solve3(T);
        if (!para.st) {
            bool spr = false;
            for (auto a: A) {
                for (auto b: B2) {
                    // cout << "a = " << a << " b = " << b << '\n';
                    vector<prostokat> vec;
                    for (auto p: T) {
                        if (!check(p, {a, b})) vec.pb(p);
                    }
                    para = solve3(vec);
                    if (para.st) {
                        (para.nd).pb({a, b});
                        spr = true;
                        // cout << "XD" << '\n';
                    }
                    if (spr) break;
                }
                if (spr) break;
            }
            for (auto a: A2) {
                for (auto b: B) {
                    if (spr) break;
                    vector<prostokat> vec;
                    for (auto p: T) {
                        if (!check(p, {a, b})) vec.pb(p);
                    }
                    para = solve3(vec);
                    if (para.st) {
                        (para.nd).pb({a, b});
                        spr = true;
                    }
                    if (spr) break;
                }
                if (spr) break;
            }
        }
    }
    // if (para.st) {
    //     cout << "OK" << '\n';
    // }
    // else {
    //     cout << "ZLE" << '\n';
    // }
    for (auto p: para.nd) {
        cout << p.x << " " << p.y << '\n';
    }
    return 0;
}

• 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: 0 / 79