oj.uz

답안 #1101702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1101702 2024-10-16T16:12:37 Z hungeazy Park (BOI16_park) C++17
27 / 100
 716 ms 56088 KB 
/*
* @Author: hungeazy
* @Date:   2024-10-16 09:41:25
* @Last Modified by:   hungeazy
* @Last Modified time: 2024-10-16 13:30:34
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
// #pragma GCC optimize("O3")  
// #pragma GCC optimize("unroll-loops")  
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
using namespace std;
using namespace __gnu_pbds; 
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ll long long 
#define ull unsigned long long
#define sz(x) x.size()
#define sqr(x) (1LL * (x) * (x))
#define all(x) x.begin(), x.end()
#define fill(f,x) memset(f,x,sizeof(f))
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define debug(x) cout << #x << " = " << x << '\n'
#define ii pair<int,int>
#define iii pair<int,ii>
#define di pair<ii,ii>
#define vi vector<int>
#define vii vector<ii>
#define mii map<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define fi first
#define se second
#define pb push_back
#define MOD 1000000007
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define MASK(i) (1LL << (i))
#define c_bit(i) __builtin_popcountll(i)
#define BIT(x,i) ((x) & MASK(i))
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define oo 1e18
#define name "ESCAPING"
#define endl '\n'
#define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms.";
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
const int N = (int)1e6+10;
int n,m,W,H;

struct Circle {

	int x,y,r;

	Circle(int _x, int _y, int _r): x(_x), y(_y), r(_r) {};

};

struct Visitor {

	int r, gate, id;

	Visitor(int _r, int _gate, int _id): r(_r), gate(_gate), id(_id) {};

	bool operator<(const Visitor &other) const {
		return r < other.r;
	}

};

struct Event {

	int r,u,v;

	Event(int _r, int _u, int _v): r(_r), u(_u), v(_v) {};

	bool operator<(const Event &other) const {
		return r < other.r;
	}

};

vector<Circle> circle;
vector<Visitor> visitor;
vector<Event> event;

namespace hungeazy {

	int par[N],sz[N],ans[N][5];

	bool check(int lim, int u, int v)
	{
		if (u >= n)
		{
			if (v >= n) return true;
			if (u == n) return circle[v].y-circle[v].r >= 2*lim; //goc duoi
			if (u == n+1) return W-(circle[v].x+circle[v].r) >= 2*lim; //goc phai
			if (u == n+2) return H-(circle[v].y+circle[v].r) >= 2*lim; //goc tren
			if (u == n+3) return circle[v].x-circle[v].r >= 2*lim; //goc trai 
			return false;
		}
		if (v >= n) return check(lim,v,u);
		int dx = circle[u].x-circle[v].x, dy = circle[u].y-circle[v].y, dis = sqr(dx)+sqr(dy);
		return dis >= sqr(circle[u].r+circle[v].r+2*lim);
	}

	int acs(int u)
	{
		return (u == par[u] ? u : par[u] = acs(par[u]));
	}

	void join(int u, int v)
	{
		int x = acs(u), y = acs(v);
		if (x != y)
		{
			if (sz[x] < sz[y]) swap(x,y);
			sz[x] += sz[y];
			par[y] = x;
		}
	}

	bool pass(int x, int y, int gate)
	{
		return acs(n+(gate+x)%4) == acs(n+(gate+y)%4);
	}

	void solve(void)
	{
		FOR(i,0,n+3) par[i] = i, sz[i] = 1;
		sort(all(visitor));
		FOR(i,0,n+3)
			FOR(j,i+1,n+3)
			{
				int l = 0, r = W+H, ans = 0;
				while (l <= r)
				{
					int mid = (l+r)>>1;
					if (check(mid,i,j)) ans = mid, l = mid+1;
					else r = mid-1;
				}
				event.pb(Event(ans,i,j));
			}
		sort(all(event));
		int i = 0;
		for (auto cur : visitor)
		{
			while (i < event.size() and event[i].r < cur.r)
			{
				join(event[i].u,event[i].v);
				i++;
			}
			int gate = cur.gate-1;
			ans[cur.id][gate] = true;
			if (!pass(0,1,gate) and !pass(0,2,gate) and !pass(0,3,gate)) ans[cur.id][(gate+1)%4] = true;
			if (!pass(0,2,gate) and !pass(1,2,gate) and !pass(0,3,gate)) ans[cur.id][(gate+2)%4] = true;
			if (!pass(0,3,gate) and !pass(2,3,gate) and !pass(1,3,gate)) ans[cur.id][(gate+3)%4] = true;
		}
		FOR(i,1,m)
		{
			FOR(j,0,3)
				if (ans[i][j]) cout << j+1;
			cout << endl;
		}
	}
	
}

signed main()
{
    fast;
    if (fopen(name".inp","r"))
    {
    	freopen(name".inp","r",stdin);
    	freopen(name".out","w",stdout);
    }
    cin >> n >> m >> W >> H;
    FOR(i,1,n) 
    {
    	int x,y,r;
    	cin >> x >> y >> r;
    	circle.pb(Circle(x,y,r));
    }
    FOR(i,1,m)
    {
    	int x,y;
    	cin >> x >> y;
    	visitor.pb(Visitor(x,y,i));
    }
    hungeazy::solve();
    time();
    return 0;
}
// ██░ ██  █    ██  ███▄    █   ▄████
//▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
//▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
//░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
//░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
// ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
// ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
// ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
// ░  ░  ░   ░              ░       ░

Compilation message

park.cpp: In function 'void hungeazy::solve()':
park.cpp:151:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |    while (i < event.size() and event[i].r < cur.r)
      |           ~~^~~~~~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:177:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |      freopen(name".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
park.cpp:178:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |      freopen(name".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 702 ms 55988 KB Output is correct
2 Correct 693 ms 55992 KB Output is correct
3 Correct 716 ms 55992 KB Output is correct
4 Correct 701 ms 55992 KB Output is correct
5 Correct 704 ms 55992 KB Output is correct
6 Correct 709 ms 56088 KB Output is correct
7 Correct 649 ms 56060 KB Output is correct
8 Correct 634 ms 56028 KB Output is correct
9 Correct 1 ms 4436 KB Output is correct
10 Correct 1 ms 4436 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 13756 KB Output is correct
2 Correct 46 ms 13768 KB Output is correct
3 Incorrect 44 ms 13724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 702 ms 55988 KB Output is correct
2 Correct 693 ms 55992 KB Output is correct
3 Correct 716 ms 55992 KB Output is correct
4 Correct 701 ms 55992 KB Output is correct
5 Correct 704 ms 55992 KB Output is correct
6 Correct 709 ms 56088 KB Output is correct
7 Correct 649 ms 56060 KB Output is correct
8 Correct 634 ms 56028 KB Output is correct
9 Correct 1 ms 4436 KB Output is correct
10 Correct 1 ms 4436 KB Output is correct
11 Correct 44 ms 13756 KB Output is correct
12 Correct 46 ms 13768 KB Output is correct
13 Incorrect 44 ms 13724 KB Output isn't correct
14 Halted 0 ms 0 KB -