Submission #1020167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020167		bachhoangxuan	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	147 ms	36492 KiB

hamburg

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int inf = 1e9;

struct rec{
    int l,r,u,d;
    rec(int l=0,int r=0,int u=0,int d=0):l(l),r(r),u(u),d(d){}
};

int N,K;
vector<rec> A;

void solve(){

}

bool check=false;
vector<pair<int,int>> cur;

vector<rec> get(int x,int y,vector<rec> a){
    cur.push_back({x,y});
    vector<rec> res;
    for(auto [l,r,u,d]:a) if(x<l || r<x || y<d || u<y) res.push_back(rec(l,r,u,d));
    return res;
}

void dfs(int k,vector<rec> a){
    if(check) return;
    if(!k){
        if(!a.empty() || check) return;
        check=true;
        for(auto [x,y]:cur) cout << x << ' ' << y << '\n';
        return;
    }
    int L=0,R=inf,U=inf,D=0;
    for(auto [l,r,u,d]:a) L=max(L,l),R=min(R,r),U=min(U,u),D=max(D,d);
    dfs(k-1,get(L,U,a));cur.pop_back();
    dfs(k-1,get(L,D,a));cur.pop_back();
    dfs(k-1,get(R,U,a));cur.pop_back();
    dfs(k-1,get(R,D,a));cur.pop_back();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> K;
    for(int i=0;i<N;i++){
        int l,r,u,d;cin >> l >> d >> r >> u;
        A.push_back(rec(l,r,u,d));
    }
    dfs(K,A);
    if(check) return 0;
    solve();
}

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