Submission #258843

#	Time	Username	Problem	Language	Result	Execution time	Memory
258843		Saboon	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	2818 ms	12780 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;

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

int L[maxn], R[maxn], D[maxn], U[maxn];
int mark[maxn];
pair<int,int> ans[5];
int rot = 0;
int p[maxn], q[6][maxn], sz = 0;

inline bool check(int,int,int,int);

bool solve(int n, int k){
	if (k == 1){
		bool cor = 1;
		int x = inf-1, y = inf-1;
		for (int i = 1; i <= sz; i++)
			x = min(x, R[p[i]]), y = min(y, U[p[i]]);
		for (int i = 1; i <= sz; i++)
			cor &= (L[p[i]] <= x and x <= R[p[i]] and D[p[i]] <= y and y <= U[p[i]]);
		if (cor)
			ans[k] = {x,y};
		return cor;
	}
	if (k == 2){
		int x = inf-1, y1 = inf-1, y2 = 1;
		for (int i = 1; i <= sz; i++)
			x = min(x, R[p[i]]), y1 = min(y1, U[p[i]]), y2 = max(y2, D[p[i]]);
		bool ret = check(n, k, x, y1);
		if (ret == true)
			return true;
		ret = check(n, k, x, y2);
		return ret;
	}
	if (k == 3){
		int x1 = inf-1, x2 = 1, y1 = inf-1, y2 = 1;
		for (int i = 1; i <= sz; i++)
			x1 = min(x1, R[p[i]]), x2 = max(x2, L[p[i]]), y1 = min(y1, U[p[i]]), y2 = max(y2, D[p[i]]);
		bool ret = check(n, k, x1, y1);
		if (ret == true)
			return true;
		ret = check(n, k, x1, y2);
		if (ret == true)
			return true;
		ret = check(n, k, x2, y1);
		if (ret == true)
			return true;
		ret = check(n, k, x2, y2);
		return ret;
	}
	if (k == 4){
		int x = inf-1;
		for (int i = 1; i <= n; i++)
			x = min(x, R[i]);
		vector<pair<int,int>> seg;
		for (int i = 1; i <= n; i++)
			if (L[i] <= x)
				seg.push_back({D[i],i});
		sort(seg.rbegin(), seg.rend());
		int minl = inf;
		for (auto it : seg){
			int idx = it.second;
			if (U[idx] < minl){
				bool ret = check(n, k, x, U[idx]);
				if (ret)
					return true;
				minl = U[idx];
			}
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			if (L[i] <= x)
				seg[cnt++] = {U[i],i};
		sort(seg.begin(), seg.end());
		int maxr = 0;
		for (auto it : seg){
			int idx = it.second;
			if (maxr < D[idx]){
				bool ret = check(n, k, x, D[idx]);
				if (ret)
					return true;
				maxr = D[idx];
			}
		}
		if (rot < 4){
			for (int i = 1; i <= n; i++){
				int l = L[i], r = R[i], u = U[i], d = D[i];
				U[i] = inf - l, D[i] = inf - r, L[i] = d, R[i] = u;
			}
			rot ++;
			bool ret = solve(n,k);
			if (ret == true){
				for (int i = 1; i <= k; i++){
					int x = ans[i].first, y = ans[i].second;
					ans[i] = {inf - y, x};
				}
				return true;
			}
		}
	}
	return false;
}

inline bool check(int n, int k, int x, int y){
	for (int i = 1; i <= sz; i++)
		q[k][i] = p[i];
	int then = 0;
	for (int it = 1; it <= sz; it++){
		int i = p[it];
		if (L[i] > x or x > R[i] or D[i] > y or y > U[i])
			p[++then] = i;
	}
	int tmp = sz;
	sz = then;
	ans[k] = {x,y};
	bool ret = solve(n, k-1);
	if (ret == true)
		return true;
	for (int i = 1; i <= tmp; i++)
		p[i] = q[k][i];
	sz = tmp;
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d%d%d%d", &L[i], &D[i], &R[i], &U[i]);
	for (int i = 1; i <= n; i++)
		p[++sz] = i;
	bool solved = solve(n, k);
	assert(solved);
	for (int i = 1; i <= k; i++)
		printf("%d %d\n", ans[i].first, ans[i].second);
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |   scanf("%d%d%d%d", &L[i], &D[i], &R[i], &U[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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