Submission #1038867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038867		hotboy2703	Hamburg Steak (JOI20_hamburg)	C++17	6 / 100	90 ms	49184 KiB

hamburg

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e18;
struct rec{
    ll l,r,d,u;
    rec(ll l1= 0,ll r1 = 0,ll d1 = 0,ll u1 = 0):l(l1),r(r1),d(d1),u(u1){}
};
namespace SCC{

}
vector <rec> A;
ll n,k;
vector <pll> ans;
bool done = 0;
vector <rec> del(vector <rec> a,pll y){
    vector <rec> res;
    for (auto x:a){
        if (x.l <= y.fi && x.r >= y.fi &&
            x.d <= y.se && x.u >= y.se){}
        else res.emplace_back(x);
    }
    return res;
}
void brute(vector <rec> cur,vector <pll> c){
    if (done)return;
    if (sz(c)==k||cur.empty()){
        while (sz(c) < k){c.push_back(MP(0,0));}
        if (cur.empty()){
            for (ll i = 0;i < k;i ++)cout<<c[i].fi<<' '<<c[i].se<<'\n';
            done = 1;
        }
        return;
    }
    ll L=0,R=INF,D=0,U=INF;
    for (auto x:A){
        L = max(x.l,L);
        R = min(x.r,R);
        D = max(x.d,D);
        U = min(x.u,U);
    }
    {
        auto tmp = MP(L,D);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
    {
        auto tmp = MP(L,U);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
    {
        auto tmp = MP(R,D);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
    {
        auto tmp = MP(R,U);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>k;
    A.resize(n);
    for (auto &x:A)cin>>x.l>>x.d>>x.r>>x.u;
    brute(A,ans);
    if (done)return 0;
    return 0;
}

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