| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258543 |
2020-08-06T06:04:14 Z |
송준혁(#5060) |
Park (BOI16_park) |
C++17 |
|
2500 ms |
23292 KB |
#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, Q, W, H;
int P[2020];
bool chk[2020];
LL X[2020], Y[2020], R[2020], A[6];
LL D[2020][2020];
int rt(int u){
if (P[u] == u) return u;
return P[u] = rt(P[u]);
}
int main(){
scanf("%d %d", &N, &Q);
scanf("%d %d", &W, &H);
for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
LL lo=0, hi=500'000'000;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) D[i][j] = (X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if (D[i][j]<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0 && chk[rt(i)]) {tf = true; break;}
if (tf) A[0]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=500'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if (D[i][j]<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0 && chk[rt(i)]) {tf = true; break;}
if (tf) A[1]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=500'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if (D[i][j]<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
if (tf) A[2]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=500'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if (D[i][j]<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
if (tf) A[3]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=500'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if (D[i][j]<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W && chk[rt(i)]) {tf = true; break;}
if (tf) A[4]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=500'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if (D[i][j]<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
if (tf) A[5]=m, hi=m-1;
else lo=m+1;
}
while (Q--){
int x, y;
scanf("%d %d", &x, &y);
if (y == 1){
printf("1");
if (x < A[0] && x < A[1] && x < A[5]) printf("2");
if (x < A[0] && x < A[2] && x < A[4] && x < A[5]) printf("3");
if (x < A[0] && x < A[3] && x < A[4]) printf("4");
}
if (y == 2){
if (x < A[0] && x < A[1] && x < A[5]) printf("1");
printf("2");
if (x < A[1] && x < A[2] && x < A[4]) printf("3");
if (x < A[1] && x < A[3] && x < A[4] && x < A[5]) printf("4");
}
if (y == 3){
if (x < A[2] && x < A[0] && x < A[5] && x < A[4]) printf("1");
if (x < A[1] && x < A[2] && x < A[4]) printf("2");
printf("3");
if (x < A[2] && x < A[3] && x < A[5]) printf("4");
}
if (y == 4){
if (x < A[0] && x < A[3] && x < A[4]) printf("1");
if (x < A[1] && x < A[3] && x < A[4] && x < A[5]) printf("2");
if (x < A[2] && x < A[3] && x < A[5]) printf("3");
printf("4");
}
printf("\n");
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:31:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:48:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:65:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:82:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:99:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:116:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
park.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &W, &H);
~~~~~^~~~~~~~~~~~~~~~~
park.cpp:27:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1562 ms |
23176 KB |
Output is correct |
| 2 |
Correct |
1501 ms |
23288 KB |
Output is correct |
| 3 |
Correct |
1488 ms |
23292 KB |
Output is correct |
| 4 |
Correct |
1500 ms |
23168 KB |
Output is correct |
| 5 |
Correct |
1510 ms |
23288 KB |
Output is correct |
| 6 |
Correct |
1522 ms |
23184 KB |
Output is correct |
| 7 |
Execution timed out |
2581 ms |
23168 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
1732 KB |
Output is correct |
| 2 |
Correct |
56 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
55 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
57 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
56 ms |
1656 KB |
Output is correct |
| 6 |
Correct |
70 ms |
1656 KB |
Output is correct |
| 7 |
Correct |
38 ms |
636 KB |
Output is correct |
| 8 |
Correct |
38 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1562 ms |
23176 KB |
Output is correct |
| 2 |
Correct |
1501 ms |
23288 KB |
Output is correct |
| 3 |
Correct |
1488 ms |
23292 KB |
Output is correct |
| 4 |
Correct |
1500 ms |
23168 KB |
Output is correct |
| 5 |
Correct |
1510 ms |
23288 KB |
Output is correct |
| 6 |
Correct |
1522 ms |
23184 KB |
Output is correct |
| 7 |
Execution timed out |
2581 ms |
23168 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
