Submission #253819

#	Time	Username	Problem	Language	Result	Execution time	Memory
253819		TadijaSebez	Hamburg Steak (JOI20_hamburg)	C++11	21 / 100	3066 ms	6368 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int lim=1e9;
array<int,4> rec[N],ans[4];
array<int,4> sec(array<int,4> a,array<int,4> b){
	return {max(a[0],b[0]),max(a[1],b[1]),min(a[2],b[2]),min(a[3],b[3])};
}
bool is_valid(array<int,4> x){
	return x[0]<=x[2]&&x[1]<=x[3];
}
int main(){
	int n,k;
	scanf("%i %i",&n,&k);
	vector<int> ids;
	for(int i=1;i<=n;i++){
		scanf("%i %i %i %i",&rec[i][0],&rec[i][1],&rec[i][2],&rec[i][3]);
		ids.pb(i);
	}
	mt19937 rng(time(0));
	shuffle(ids.begin(),ids.end(),rng);
	while(1){
		vector<int> v[2];
		for(int i=0;i<k;i++)ans[i]={1,1,lim,lim};
		for(int i:ids){
			bool ok=0;
			for(int j=0;j<k;j++){
				if(is_valid(sec(ans[j],rec[i]))){
					ans[j]=sec(ans[j],rec[i]);
					ok=1;v[0].pb(i);
					break;
				}
			}
			if(!ok)v[1].pb(i);
		}
		if(v[1].empty()){
			for(int i=0;i<k;i++)printf("%i %i\n",ans[i][0],ans[i][1]);
			return 0;
		}
		ids=v[1];
		shuffle(ids.begin(),ids.end(),rng);
		for(int i:v[0])ids.pb(i);
	}
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%i %i",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
hamburg.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   scanf("%i %i %i %i",&rec[i][0],&rec[i][1],&rec[i][2],&rec[i][3]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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