Submission #259454

#	Time	Username	Problem	Language	Result	Execution time	Memory
259454		shayan_p	Hamburg Steak (JOI20_hamburg)	C++14	6 / 100	103 ms	8816 KiB

hamburg

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii, pii> rect;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9;

rect operator & (rect a, rect b){
    return { {max(a.F.F, b.F.F), max(a.F.S, b.F.S)}, {min(a.S.F, b.S.F), min(a.S.S, b.S.S)} };
}
bool inside(rect a, rect b){// b inside a
    return a.F.F < b.F.F && a.F.S < b.F.S && b.S.F < a.S.F && b.S.S < a.S.S;
}
bool inside(rect a, pii b){
    return a.F.F <= b.F && b.F <= a.S.F && a.F.S <= b.S && b.S <= a.S.S;
}

rect big = { {1, 1}, {inf, inf} };

int choose_and_del(vector<pii> &v){
    if(v.empty())
	return 1;
    int x = v[0].S;
    for(pii p : v)
	x = min(x, p.S);
    vector<pii> v2;
    for(pii p : v){
	if(x < p.F)
	    v2.PB(p);
    }
    v = v2;
    return x;
}
bool ok(vector<rect> &inp, vector<pii> &ans){
    for(auto a : inp){
	bool is = 0;
	for(auto b : ans)
	    is|= inside(a, b);
	if(!is)
	    return 0;
    }
    return 1;
}
vector<rect> del(vector<rect> &inp, pii p){
    vector<rect> ans;
    for(auto r : inp){
	if(inside(r, p) == 0)
	    ans.PB(r);
    }
    return ans;
}

pair<bool, vector<pii> > solve(vector<rect> inp, int k){
    vector<pii> ans;
    
    rect r = big;
    for(auto x : inp)
	r = r & x;
    if(r.F.F <= r.S.F){
	vector<pii> v;
	for(rect r : inp)
	    v.PB({r.F.S, r.S.S});
	for(int i = 0; i < k; i++)
	    ans.PB({r.F.F, choose_and_del(v)});
	if(v.empty())
	    return {1, ans};
	else
	    ans.clear();
	return {0, ans};
    }
    if(r.F.S <= r.S.S){
	vector<pii> v;
	for(rect r : inp)
	    v.PB({r.F.F, r.S.F});
	for(int i = 0; i < k; i++)
	    ans.PB({choose_and_del(v), r.F.S});
	if(v.empty())
	    return {1, ans};
	else
	    ans.clear();
	return {0, ans};	
    }
    if(k == 1){
	return {0, ans};
    }
    
    swap(r.F, r.S);
    for(rect p : inp){
	if(inside(r, p))
	    return {0, ans};
    }

    if(k == 2){
	ans.PB(r.F);
	ans.PB(r.S);
	if(ok(inp, ans))
	    return {1, ans};
	swap(ans[0].S, ans[1].S);
	if(ok(inp, ans))
	    return {1, ans};
	ans.clear();
	return {0, ans};
    }

    for(int x : {r.F.F, r.S.F})
	for(int y : {r.F.S, r.S.S}){
	    auto p = solve(del(inp, {x, y}), k-1);
	    if(p.F){
		p.S.PB({x, y});
		return p;
	    }
	}
    return {0, ans};   	    
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, k;
    cin >> n >> k;
    vector< rect > inp(n);
    for(int i = 0; i < n; i++){
	cin >> inp[i].F.F >> inp[i].F.S >> inp[i].S.F >> inp[i].S.S;
    }
    auto _ = solve(inp, k);
    vector<pii> v = _.S;
    if(_.F)
	assert(sz(v) == k);
    for(pii p : v)
	cout << p.F << " " << p.S << "\n";
    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