Submission #961692

#	Time	Username	Problem	Language	Result	Execution time	Memory
961692		Vladth11	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	65 ms	15956 KiB

hamburg

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#define int ll

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 200001;
const ll INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

struct rect {
    int x1, y1, x2, y2;
} v[NMAX];

int n, k;
vector <pii> sol;
int taken[NMAX];

rect intersect(rect a, rect b) {
    rect sol = {max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2)};
    return sol;
}

bool isIn(pii a, rect r) {
    return (r.x1 <= a.first && a.first <= r.x2 && r.y1 <= a.second && a.second <= r.y2);
}

rect solve1() {
    int i;
    rect sol = {0, 0, INF, INF};
    for(i = 1; i <= n; i++) {
        sol = intersect(sol, v[i]);
    }
    return sol;
}

void afiseaza() {
    for(auto x : sol) {
        cout << x.first << " " << x.second << "\n";
    }
    k -= sol.size();
    while(k--) {
        cout << "0 0\n";
    }
    exit(0);
}

void tryy(int lvl) {
    int i;
    if(lvl == 0) {
        int ok = 1;
        for(i = 1; i <= n; i++) {
            ok &= taken[i];
        }
        if(ok) {
            afiseaza();
        }
        return;
    }
    int xmin = 2e9, xmax = 0, ymin = 2e9, ymax = 0;
    for(i = 1; i <= n; i++) {
        if(taken[i]) continue;
        xmin = min(xmin, v[i].x2);
        xmax = max(xmax, v[i].x1);
        ymin = min(ymin, v[i].y2);
        ymax = max(ymax, v[i].y1);
    }
    vector <pii> per;
    per.push_back({xmin, ymin});
    per.push_back({xmin, ymax});
    per.push_back({xmax, ymin});
    per.push_back({xmax, ymax});
    for(int d = 0; d < 4; d++) {
        pii acum = per[d];
        for(i = 1; i <= n; i++) {
            if(isIn(acum, v[i])) {
                taken[i]++;
            }
        }
        sol.push_back(acum);
        tryy(lvl - 1);
        for(i = 1; i <= n; i++) {
            if(isIn(acum, v[i])) taken[i]--;
        }
        sol.pop_back();
    }
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n >> k;
    for(i = 1; i <= n; i++) {
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2; /// it doesn't matter
    }
    /// K = 1?
    tryy(1);
    /// K = 2?
    tryy(2);
    /// K = 3?
    tryy(3);
    /// K = 4 and pair found
    tryy(4);
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 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