Submission #260224

#	Time	Username	Problem	Language	Result	Execution time	Memory
260224		shayan_p	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	3067 ms	20168 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)} };
}
pii operator & (pii a, pii b){
    return {max(a.F, b.F), min(a.S, b.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;
}
bool emp(rect a){
    return a.F.F > a.S.F || a.F.S > a.S.S;
}
bool emp(pii a){
    return a.F > a.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;
}
/*
bool delta(vector<pii> &v){
    if(v.empty()){
	v.PB({1, inf});
	v.PB({1, inf});
	return 1;
    }
    vector<pii> ans;
    while(sz(v) < 2)
	v.PB(v.back());
    for(int i = 1; i < sz(v); i++)
	if(v[i].S < v[0].S)
	    swap(v[i], v[0]);
    for(int i = 2; i < sz(v); i++)
	if(v[1].F < v[i].F)
	    swap(v[i], v[1]);
    if(v[1].F <= v[0].S){
	int L = v[1].F, R = v[0].S;
	ans.PB({v[1].F, v[0].S});
	ans.PB({1, inf});
	v[1].F = R + 1;
	v[0].S = L - 1;
	for(pii p : v){
	    if((v[0] & p) == v[0] || (v[1] & p == v[1]))
		continue;	    
	}
	if(v[0].F <= v[0].S && v[1].F <= v[1].S)
		    
    }
    else{
    }
}
*/

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);
    
    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;
	    }
	}
    if(k == 3){
	return {0, ans};
    }

    
    //    now k == 4
    
    //    vector<pii> UD, LR;
    
    rect D = {r.F, {r.S.F, r.F.S}}, U = {{r.F.F, r.S.S}, r.S}, L = {r.F, {r.F.F, r.S.S}}, R = {{r.S.F, r.F.S}, r.S};

    int BEF = 0;
    for(int w = 0; w < 50; w++){
	int NW = 0;	
	random_shuffle(inp.begin(), inp.end());
	for(rect p : inp){
	    rect eD = D & p, eU = U & p, eL = L & p, eR = R & p;
	    int C = emp(eD) + emp(eU) + emp(eL) + emp(eR);
	    if(C == 4)
		return {0, ans};
	    if(C == 3){
		NW++;
		
		if(!emp(eD))
		    D = eD;
		if(!emp(eU))
		    U = eU;
		if(!emp(eL))
		    L = eL;
		if(!emp(eR))
		    R = eR;
	    }
	    /*	    if(C == 2){
		if(!emp(eD) && !emp(eU))
		    UD.PB({p.F.F, p.S.F});
		if(!emp(eL) && !emp(eR))
		    LR.PB({p.F.S, p.S.S});	    
		    }*/
	    if(NW == BEF)
		break;
	    BEF = NW;
	}
    }
    if(emp(D) || emp(U) || emp(L) || emp(R)){
	return {0, ans};
    }
    /*
    if(!delta(UD))
	return {0, ans};
    if(!delta(LR))
	return {0, ans};
    */

    while(true){
	random_shuffle(inp.begin(), inp.end());
	rect r = D;
	vector<rect> inp2;	
	for(rect p : inp){
	    if(emp(p & r))
		inp2.PB(p);
	    else
		r = p & r;	    
	}
	auto x = solve(inp2, k-1);
	if(x.F){
	    x.S.PB(r.F);
	    return {1, x.S};
	}
    }	
}

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

    srand(time(0));
    
    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;
    assert(_.F);
    for(pii p : v)
	cout << p.F << " " << p.S << "\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