제출 #651894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651894		ymm	Park (BOI16_park)	C++17	0 / 100	727 ms	49784 KiB

park

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2048;
const int M = 100'010;

vector<pair<pll,pii>> dis2;
vector<pair<ll,int>> vis;
int ans[N], vr[N], vent[N];

int par[N];
int rt(int v){return par[v]==v?v:(par[v]=rt(par[v]));}
void unite(int v, int u)
{
	v = rt(v);
	u = rt(u);
	par[u] = v;
}

ll Ox[N], Oy[N], Or[N];
ll W, H;
int n, m;

ll sqr(ll x){return x*x;}

bool cmp (pll _x, pll _y)
{
	pair<__int128, __int128> x = _x;
	pair<__int128, __int128> y = _y;
	auto mn = min(x.second, y.second);
	x.second -= mn;
	y.second -= mn;
	if (x.first != 0 && y.first != 0) {
		x = {4*sqr(x.second)*x.first, x.first + sqr(x.second)}; // 0, 1e18
		y = {4*sqr(y.second)*y.first, y.first + sqr(y.second)}; // 1e36, 1e18
	}
	if (x.first == 0) {
		x.second -= y.second;
		y.second = 0;
		if (x.second < 0)
			return 1;
		return sqr(x.second) < y.first;
	} else {
		y.second -= x.second;
		x.second = 0;
		if (y.second < 0)
			return 0;
		return x.first < sqr(y.second);
	}
}

bool cmp_wrap(const pair<pll,pii> &x, const pair<pll,pii> &y)
{
	return cmp(x.first, y.first);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	cin >> W >> H;
	Loop (i,0,n) 
		cin >> Ox[i] >> Oy[i] >> Or[i];
	Loop (i,0,m) {
		cin >> vr[i] >> vent[i];
		--vent[i];
	}
	Loop (i,0,n) {
		dis2.push_back({{0, Oy[i] - Or[i]}, {i+4, 0}});
		dis2.push_back({{0, W - Ox[i] - Or[i]}, {i+4, 1}});
		dis2.push_back({{0, H - Oy[i] - Or[i]}, {i+4, 2}});
		dis2.push_back({{0, Ox[i] - Or[i]}, {i+4, 3}});
	}
	Loop (i,0,n) Loop (j,i+1,n) {
		ll sdis = sqr(Ox[i] - Ox[j]) + sqr(Oy[i] - Oy[j]);
		ll dis = - Or[i] - Or[j];
		dis2.push_back({{sdis, dis}, {i+4, j+4}});
	}
	Loop (i,0,m)
		vis.push_back({vr[i], i});
	sort(dis2.rbegin(), dis2.rend(), cmp_wrap);
	sort(vis.rbegin(), vis.rend());
	iota(par, par+N, 0);
	while (vis.size()) {
		auto [r2, i] = vis.back();
		vis.pop_back();
		r2 *= 2;
		while (dis2.size() && cmp(dis2.back().first, {0, r2})) {
			auto [v, u] = dis2.back().second;
			unite(v, u);
			dis2.pop_back();
		}
		int e = vent[i];
		int s0 = rt(e+0 & 3);
		int s1 = rt(e+1 & 3);
		int s2 = rt(e+2 & 3);
		int s3 = rt(e+3 & 3);
		ans[i] |= (1 << (e+0 & 3));
		if (s0 != s1 && s0 != s2 && s0 != s3)
			ans[i] |= (1 << (e+1 & 3));
		if (s0 != s2 && s0 != s3 && s1 != s2 && s1 != s3)
			ans[i] |= (1 << (e+2 & 3));
		if (s3 != s0 && s3 != s1 && s3 != s2)
			ans[i] |= (1 << (e+3 & 3));
	}
	Loop (i,0,m) {
		Loop (j,0,4)
			if (ans[i] & (1 << j))
				cout << j+1;
		cout << '\n';
	}
}

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

park.cpp: In function 'int main()':
park.cpp:99:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   99 |   int s0 = rt(e+0 & 3);
      |               ~^~
park.cpp:100:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  100 |   int s1 = rt(e+1 & 3);
      |               ~^~
park.cpp:101:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  101 |   int s2 = rt(e+2 & 3);
      |               ~^~
park.cpp:102:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  102 |   int s3 = rt(e+3 & 3);
      |               ~^~
park.cpp:103:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  103 |   ans[i] |= (1 << (e+0 & 3));
      |                    ~^~
park.cpp:105:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  105 |    ans[i] |= (1 << (e+1 & 3));
      |                     ~^~
park.cpp:107:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  107 |    ans[i] |= (1 << (e+2 & 3));
      |                     ~^~
park.cpp:109:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  109 |    ans[i] |= (1 << (e+3 & 3));
      |                     ~^~

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