제출 #349411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349411		sinamhdv	Park (BOI16_park)	C++11	100 / 100	1459 ms	1644 KiB

park

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 2020

int n, m;
int w, h;
int tx[MAXN], ty[MAXN], tr[MAXN];
int ans[5][5];
int cn;
int comp[MAXN][MAXN];

int crad;

inline bool olap(int a, int b)
{
	if (a > n && b > n)
		return false;
	if (a > b)
		swap(a, b);
	if (b > n)	// C - L
	{
		b -= n;
		int d;
		if (b == 1)
			d = ty[a] - crad;
		else if (b== 2)
			d = w - tx[a] - crad;
		else if (b == 3)
			d = h - ty[a] - crad;
		else if (b == 4)
			d = tx[a] - crad;

		return (tr[a] + crad > d);
	}
	else	// C - C
	{
		int dx = abs(tx[a] - tx[b]);
		int dy = abs(ty[a] - ty[b]);
		int dr = tr[a] + tr[b] + 2 * crad;
		return ((ll)dr * dr > (ll)dx*dx + (ll)dy*dy);
	}
}

int ptr = 0;

void dfs(int v)
{
	comp[ptr][v] = cn;
	FOR(i, 1, n + 5)
	{
		if (comp[ptr][i] || !olap(v, i))
			continue;
		dfs(i);
	}
}

inline void mkcomp(int r)
{
	cn = 0;

	crad = r;

	FOR(i, 1, n + 5)
	{
		if (!comp[ptr][i])
		{
			cn++;
			dfs(i);
		}
	}
}

inline bool check(int src, int dst)
{
	if (abs(src - dst) == 2)
	{
		int x1 = src + n;
		int x2 = (src % 4) + 1 + n;
		int y1 = dst + n;
		int y2 = (dst % 4) + 1 + n;


		return (comp[ptr - 1][x1] != comp[ptr - 1][y2] && comp[ptr - 1][x1] != comp[ptr - 1][y1] && comp[ptr - 1][x2] != comp[ptr - 1][y1] && comp[ptr - 1][x2] != comp[ptr - 1][y2]);
	}
	else
	{
		if (src > dst)
			swap(src, dst);
		if (src == 1 && dst == 4)
			swap(src, dst);


		bool res = true;
		FOR(i, 1, 5)
			if (i != src)
				res &= (comp[ptr - 1][src + n] != comp[ptr - 1][i + n]);
		return res;
	}
}

int32_t main(void)
{
	//fast_io;
	scanf("%d %d %d %d", &n, &m, &w, &h);
	FOR(i, 1, n + 1)
	{
		scanf("%d %d %d", tx + i, ty + i, tr + i);
	}
/*
	while (true)
	{
		int s, d, r;
		cin >> r >> s >> d;
		cout << check(r, s, d) << endl << flush;
	}
	*/

	int qf[] = {1,1,1,2,2,3};
	int qs[] = {2,3,4,3,4,4};

	int l[] = {1, 1, 1, 1, 1, 1};
	const int mx = INF;
	int r[] = {mx, mx, mx, mx, mx, mx};
	int mid[6];

	const int LOGN = 30;

	mkcomp(1);
	ptr++;
	FOR(i, 0, 6)
	{
		if (!check(qf[i], qs[i]))
		{
			l[i] = -1;
			r[i] = -1;
		}
	}

	FOR(bsi, 0, LOGN)
	{
		vector<int> rs;
		bool as[6];
		
		FOR(i, 0, 6)
		{
			if (r[i] - l[i] > 1)
			{
				mid[i] = (l[i] + r[i]) >> 1;
				rs.pb(mid[i]);
			}
		}
		
		sort(all(rs));
		rs.resize(unique(all(rs)) - rs.begin());

		FOR(i, 0, (int)rs.size())
		{
			mkcomp(rs[i]);
			ptr++;
			FOR(j, 0, 6)
				if (mid[j] == rs[i] && r[j] - l[j] > 1)
					as[j] = check(qf[j], qs[j]);
		}
		FOR(i, 0, 6)
		{
			if (r[i] - l[i] <= 1)
				continue;
			if (as[i])
				l[i] = mid[i];
			else
				r[i] = mid[i];
		}

		dbgr(l, l + 6);
		dbgr(r, r + 6);
		dbgr(mid, mid + 6);
	}
	FOR(i, 0, 6)
		ans[qf[i]][qs[i]] = l[i];

	/*
	FOR(e1, 1, 4)
	{
		FOR(e2, e1 + 1, 5)
		{
			int l = 1, r = INF + 10;
			if (!check(l, e1, e2))
			{
				ans[e1][e2] = -1;
				continue;
			}
			while (r - l > 1)
			{
				int mid = (r + l) / 2;
				if (check(mid, e1, e2))
					l = mid;
				else
					r = mid;
			}
			ans[e1][e2] = l;
		}
	}*/



	while (m--)
	{
		int r, e;
		scanf("%d %d", &r, &e);
		char res[8] = {0,0,0,0,0,0,0,0};
		char *ptr = res;
		FOR(i, 1, 5)
		{
			if (e == i || ans[e][i] >= r || ans[i][e] >= r)
				*ptr++ = (i + '0');
		}
		puts(res);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'int32_t main()':
park.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |  scanf("%d %d %d %d", &n, &m, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |   scanf("%d %d %d", tx + i, ty + i, tr + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:235:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  235 |   scanf("%d %d", &r, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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