oj.uz

Submission #74074

# Submission time Handle Problem Language Result Execution time Memory
74074 2018-08-30T03:03:11 Z tmwilliamlin168 Park (BOI16_park) C++14
31 / 100
 2500 ms 8868 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second

const int mxN=2e3, mxM=1e5;
int n, m;
ll w, h, x[mxN], y[mxN], r[mxN], ans[4][4], dist[mxN];
bool vis[mxN];

__attribute__((always_inline)) ll c0(ll a, ll b) {
	ll lb=1, rb=1e9;
	while(lb<=rb) {
		ll mb=(lb+rb)/2;
		if((mb+b)*(mb+b)<=a)
			lb=mb+1;
		else
			rb=mb-1;
	}
	return rb;
}

ll c1(int a) {
	ll b=LLONG_MAX;
	memset(dist, 0x3F, 8*n);
	for(int i=0; i<n; ++i) {
		dist[i]=min(x[i]-r[i], dist[i]);
		dist[i]=min(h-y[i]-r[i], dist[i]);
		if(a==0)
			dist[i]=min(w-x[i]-r[i], dist[i]);
	}
	memset(vis, 0, n);
	for(int it=0; it<n; ++it) {
		int mi=-1;
		for(int i=0; i<n; ++i)
			if(!vis[i]&&(mi==-1||dist[i]<dist[mi]))
				mi=i;
		vis[mi]=1;
		for(int i=0; i<n; ++i)
			if(!vis[i])
				dist[i]=min(max(c0((x[i]-x[mi])*(x[i]-x[mi])+(y[i]-y[mi])*(y[i]-y[mi]), r[i]+r[mi]), dist[mi]), dist[i]);
		b=min(max(y[mi]-r[mi], dist[mi]), b);
		if(a==1)
			b=min(max(w-x[mi]-r[mi], dist[mi]), b);
	}
	return b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> w >> h;
	for(int i=0; i<n; ++i)
		cin >> x[i] >> y[i] >> r[i];
	for(int i=0, j=0, k=1; i<4; ++i, j^=2) {
		ans[i][i]=LLONG_MAX;
		ans[j][j^k]=ans[j^k][j]=c1(0);
		for(int l=0; l<n; ++l)
			y[l]=h-y[l];
		if(i==1) {
			ans[0][2]=ans[2][0]=c1(1);
			swap(w, h);
			for(int l=0; l<n; ++l)
				swap(x[l], y[l]);
			k^=2;
		} else if(i==0)
			ans[1][3]=ans[3][1]=c1(1);
	}
//	for(int i=0; i<4; ++i)
//		for(int j=i; j<4; ++j)
//			cout << i+1 << " " << j+1 << " " << ans[i][j] << endl;
	while(m--) {
		int ri, ei;
		cin >> ri >> ei, --ei;
		for(int i=0; i<4; ++i)
			if(2*ri<=ans[ei][i])
				cout << i+1;
		cout << "\n";
	}
}

Compilation message

park.cpp:14:35: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) ll c0(ll a, ll b) {
                                   ^~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2496 ms 444 KB Output is correct
2 Correct 2468 ms 628 KB Output is correct
3 Correct 2483 ms 816 KB Output is correct
4 Execution timed out 2517 ms 1076 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1180 KB Output is correct
2 Correct 65 ms 2340 KB Output is correct
3 Correct 65 ms 3468 KB Output is correct
4 Correct 66 ms 4460 KB Output is correct
5 Correct 66 ms 5460 KB Output is correct
6 Correct 69 ms 6864 KB Output is correct
7 Correct 39 ms 7660 KB Output is correct
8 Correct 39 ms 8868 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2496 ms 444 KB Output is correct
2 Correct 2468 ms 628 KB Output is correct
3 Correct 2483 ms 816 KB Output is correct
4 Execution timed out 2517 ms 1076 KB Time limit exceeded
5 Halted 0 ms 0 KB -