Submission #213533

#	Time	Username	Problem	Language	Result	Execution time	Memory
213533		vincent97198	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	3100 ms	6704 KiB

hamburg

#include<bits/stdc++.h>
#define ll long long
#define fo(i,x,y) for(int i=x; i<=y; i++)
using namespace std;

const int N = 2e5 + 5;

int n,k;

struct P {
	ll x1,y1,x2,y2;
} a[N];

ll query(P a) {
	if (a.x1 > a.x2)
		return 0;
	if (a.y1 > a.y2)
		return 0;
	return (a.x2 - a.x1 + 1) * (a.y2 - a.y1 + 1);
}

P merge(P a,P b) {
	a.x1 = max(a.x1,b.x1);
	a.y1 = max(a.y1,b.y1);
	a.x2 = min(a.x2,b.x2);
	a.y2 = min(a.y2,b.y2);
	return a;
}

P b[5];

#define db double

db calc(P a,P b)
{
	db s = query(a),s2 = query(merge(a,b));
	return (db)(s - s2) / s;
}

int main()
{
	srand(time(NULL));
	scanf("%d %d",&n,&k);
	fo(i,1,n)
	{
		scanf("%lld %lld %lld %lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
	}
	k = min(k,n);
	while (1)
	{
		int bz = 1;
		random_shuffle(a + 1,a + n + 1);
		fo(i,1,k) b[i] = a[i];
		fo(i,k + 1,n) {
			int x = 1;
			db y = 1e9;
			fo(j,1,k) {
				db v = calc(b[j],a[i]);
				if (v < y)
					x = j,y = v;
			}
			b[x] = merge(b[x],a[i]);
			if (query(b[x]) == 0) {
				bz = 0;
				break;
			}
		}
		if (bz)
		{
			fo(i,1,k) printf("%lld %lld\n",b[i].x1,b[i].y1);
			break;
		}
	}
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d %d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
hamburg.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |   scanf("%lld %lld %lld %lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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