Submission #74500

#	Time	Username	Problem	Language	Result	Execution time	Memory
74500		polyfish	Park (BOI16_park)	C++14	0 / 100	2242 ms	896 KiB

park

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 2007;
const int INF = 1e9;

struct circle {
	int x, y, r;

	bool intersect(circle c) {
		int64_t tmp1 = 1LL * (x - c.x) * (x - c.x) + 1LL * (y - c.y) * (y - c.y);
		int64_t tmp2 = 1LL * (r + c.r) * (r + c.r);
		return tmp1 <= tmp2;
	}
};

int n, m, w, h, max_rad[4][4], L[4];
circle c[MAX_N], c2[MAX_N];
bool visited[4][MAX_N];

void enter() {
	cin >> n >> m >> w >> h;
	for (int i=0; i<n; ++i) {
		cin >> c[i].x >> c[i].y >> c[i].r;
	}
}

void visit(int u, int root) {
	// debug(u);
	visited[root][u] = true;
	if (u==n || u==n+2) {
		for (int i=0; i<n; ++i)
			if (!visited[root][i] && abs(c2[i].y-L[u-n])<=c2[i].r)
				visit(i, root);
	}
	if (u==n+1 || u==n+3) {
		//debug(abs(c2[4].x - L[u-n]));
		//debug(L[1]);
		for (int i=0; i<n; ++i)
			if (!visited[root][i] && abs(c2[i].x-L[u-n])<=c2[i].r)
				visit(i, root);
	}
	if (u<n) {
		for (int i=0; i<n; ++i)
			if (!visited[root][i] && c2[u].intersect(c2[i]))
				visit(i, root);
		if (abs(c2[u].y-L[0])<=c2[u].r)
			visited[root][n] = true;
		if (abs(c2[u].y-L[2])<=c2[u].r)
			visited[root][n+2] = true;
		if (abs(c2[u].x-L[1])<=c2[u].r)
			visited[root][n+1] = true;
		if (abs(c2[u].x-L[3])<=c2[u].r)
			visited[root][n+3] = true;
	}
}

bool reachable(int corner1, int corner2, int cir_rad) {
	if (corner1==0 && corner2==3)
		swap(corner1, corner2);
	for (int i=0; i<n; ++i) {
		c2[i] = c[i];
		c2[i].r += cir_rad;
	}
	//debug(c2[0].r);
	memset(visited, false, sizeof(visited));
	visit(n, 0);
	visit(n+1, 1);
	visit(n+2, 2);
	visit(n+3, 3);
	// debug(visited[corner1][n+(corner1+3)%4]);
	if (visited[corner1][n+(corner1+3)%4]
		|| visited[corner2][n+(corner2+3)%4])
		return false;
	//BP();
	if ((corner1+2)%4==corner2)
		return !visited[0][n+2] && !visited[1][n+3];
	return !visited[corner1][n+(corner1+2)%4];
}

void find_maximum_circle_size(int corner1, int corner2) {
	int l = 0, r = INF;
	for (int mid=(l+r)/2; l!=mid && mid!=r; mid = (l+r)/2) {
		if (reachable(corner1, corner2, mid))
			l = mid;
		else
			r = mid;
	}
	for (int i=r; i>=l; --i) {
		if (reachable(corner1, corner2, i)) {
			max_rad[corner1][corner2] = max_rad[corner2][corner1] = i;
			return;
		}
	}
}

void solve() {
	L[0] = L[3] = 0;
	L[1] = w;
	L[2] = h;
	for (int i=0; i<4; ++i)
		for (int j=i+1; j<4; ++j)
			find_maximum_circle_size(i, j);
	debug(max_rad[0][1]);
	while (m--) {
		int r, e;
		cin >> r >> e;
		--e;
		for (int i=0; i<4; ++i)
			if (i==e || r<=max_rad[i][e])
				cout << i+1;
		cout << '\n';
	}
}

int main() {
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	solve();
	// L[0] = L[3] = 0;
	// L[1] = w;
	// L[2] = h;
	//find_maximum_circle_size(2, 3);
	//debug(reachable(2, 3, INF));
	//debug(max_rad[2][3]);
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42