Submission #1213215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213215		emptypringlescan	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	3093 ms	43512 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("bmi,bmi2,avx2,popcnt,lzcnt")
int n,k;
int arr[200005][4];
vector<pair<int,int> > ans;
bool sc(int nk){
	if(nk==0){
		for(int i=0; i<n; i++) if(arr[i][0]!=-1) return false;
		return true;
	}
	int hm[4]={-1,-1,(int)1e9,(int)1e9};
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		for(int j=0; j<2; j++){
			hm[j]=max(hm[j],arr[i][j]);
		}
		for(int j=2; j<4; j++){
			hm[j]=min(hm[j],arr[i][j]);
		}
	}
	pair<int,int> pt;
	vector<pair<int,int> > undo;
	pt={hm[0],hm[1]};
	ans.push_back(pt);
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
			undo.push_back({i,arr[i][0]});
			arr[i][0]=-1;
		}
	}
	if(sc(nk-1)) return true;
	ans.pop_back();
	for(auto i:undo) arr[i.first][0]=i.second;
	undo.clear();
	
	pt={hm[2],hm[1]};
	ans.push_back(pt);
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
			undo.push_back({i,arr[i][0]});
			arr[i][0]=-1;
		}
	}
	if(sc(nk-1)) return true;
	ans.pop_back();
	for(auto i:undo) arr[i.first][0]=i.second;
	undo.clear();
	
	pt={hm[2],hm[3]};
	ans.push_back(pt);
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
			undo.push_back({i,arr[i][0]});
			arr[i][0]=-1;
		}
	}
	if(sc(nk-1)) return true;
	ans.pop_back();
	for(auto i:undo) arr[i.first][0]=i.second;
	undo.clear();
	
	pt={hm[0],hm[3]};
	ans.push_back(pt);
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
			undo.push_back({i,arr[i][0]});
			arr[i][0]=-1;
		}
	}
	if(sc(nk-1)) return true;
	ans.pop_back();
	for(auto i:undo) arr[i.first][0]=i.second;
	undo.clear();
	return false;
}
bool delpt(pair<int,int> pt){
	vector<pair<int,int> > undo;
	ans.push_back(pt);
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
			undo.push_back({i,arr[i][0]});
			arr[i][0]=-1;
		}
	}
	if(sc(3)) return true;
	ans.pop_back();
	for(auto i:undo) arr[i.first][0]=i.second;
	undo.clear();
	return false;
}
unordered_set<int> us;
void s4(){
	int hm[4]={-1,-1,(int)1e9,(int)1e9};
	for(int i=0; i<n; i++){
		if(arr[i][0]==-1) continue;
		for(int j=0; j<2; j++){
			hm[j]=max(hm[j],arr[i][j]);
		}
		for(int j=2; j<4; j++){
			hm[j]=min(hm[j],arr[i][j]);
		}
	}
	for(int i:us){
		pair<int,int> pt;
		pt={hm[0],i};
		if(delpt(pt)) return;
		pt={hm[2],i};
		if(delpt(pt)) return;
		pt={i,hm[1]};
		if(delpt(pt)) return;
		pt={i,hm[3]};
		if(delpt(pt)) return;
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; i++) for(int j=0; j<4; j++){
		cin >> arr[i][j];
		us.insert(arr[i][j]);
	}
	if(sc(k)){
		for(auto i:ans) cout << i.first << ' ' << i.second << '\n';
	}
	else{
		ans.clear();
		s4();
		for(auto i:ans) cout << i.first << ' ' << i.second << '\n';
	}
}

• 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