Submission #258808

#	Time	Username	Problem	Language	Result	Execution time	Memory
258808		amoo_safar	Hamburg Steak (JOI20_hamburg)	C++14	15 / 100	583 ms	7764 KiB

hamburg

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, k;
int L[N], R[N], U[N], D[N];

vector<int> uX, uY;
vector<pii> points;

void Done(){
	for(auto x : points) printf("%d %d\n", uX[x.F], uY[x.S]);
	exit(0);
}

int mk[N];

void On(pii P, int col){
	for(int i = 0; i < n; i++){
		if(L[i] <= P.F && P.F <= R[i] && D[i] <= P.S && P.S <= U[i] && !mk[i]) mk[i] = col;
	}
	points.pb(P);
}
void Off(int col){
	for(int i = 0; i < n; i++)
		if(mk[i] == col)
			mk[i] = 0;
	points.pop_back();
}

void Solve(int y){
	if(y == 0){
		for(int i = 0; i < n; i++)
			if(!mk[i])
				return ;
	}
	int mnx = N, mxx = -1;
	for(int i = 0; i < n; i++)
		if(!mk[i])
			mnx = min(mnx, R[i]), mxx = max(mxx, L[i]);
	if(mxx == -1){
		for(int i = 0; i < y; i++) points.pb(pii(0, 0));
		Done();
	}


	int mny = N, mxy = -1;
	for(int i = 0; i < n; i++)
		if(!mk[i])
			mny = min(mny, U[i]), mxy = max(mxy, D[i]);
	
	for(int px : {mnx, mxx}){
		for(int py : {mny, mxy}){
			On({px, py}, y);
			Solve(y - 1);
			Off(y);
		}
	}

}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++) scanf("%d%d%d%d", L + i, D + i, R + i, U + i);

	for(int i = 0; i < n; i++) uX.pb(L[i]), uY.pb(D[i]), uX.pb(R[i]), uY.pb(U[i]);
	
	sort(all(uX)); uX.resize(unique(all(uX)) - uX.begin());
	sort(all(uY)); uY.resize(unique(all(uY)) - uY.begin());

	for(int i = 0; i < n; i++){
		L[i] = lower_bound(all(uX), L[i]) - uX.begin();
		R[i] = lower_bound(all(uX), R[i]) - uX.begin();
		U[i] = lower_bound(all(uY), U[i]) - uY.begin();
		D[i] = lower_bound(all(uY), D[i]) - uY.begin();
	}

	assert(k <= 3);

	Solve(k);
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:84:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  for(int i = 0; i < n; i++) 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: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79