| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 258544 |
2020-08-06T06:06:37 Z |
송준혁(#5060) |
Park (BOI16_park) |
C++17 |
|
2500 ms |
23288 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=250'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=250'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=250'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=250'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=250'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=250'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);
~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1419 ms |
23288 KB |
Output is correct |
| 2 |
Correct |
1406 ms |
23168 KB |
Output is correct |
| 3 |
Correct |
1369 ms |
23288 KB |
Output is correct |
| 4 |
Correct |
1355 ms |
23160 KB |
Output is correct |
| 5 |
Correct |
1377 ms |
23160 KB |
Output is correct |
| 6 |
Correct |
1359 ms |
23288 KB |
Output is correct |
| 7 |
Execution timed out |
2573 ms |
23180 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
76 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
59 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
55 ms |
1616 KB |
Output is correct |
| 4 |
Correct |
54 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
54 ms |
1656 KB |
Output is correct |
| 6 |
Correct |
65 ms |
1656 KB |
Output is correct |
| 7 |
Correct |
38 ms |
632 KB |
Output is correct |
| 8 |
Correct |
39 ms |
636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1419 ms |
23288 KB |
Output is correct |
| 2 |
Correct |
1406 ms |
23168 KB |
Output is correct |
| 3 |
Correct |
1369 ms |
23288 KB |
Output is correct |
| 4 |
Correct |
1355 ms |
23160 KB |
Output is correct |
| 5 |
Correct |
1377 ms |
23160 KB |
Output is correct |
| 6 |
Correct |
1359 ms |
23288 KB |
Output is correct |
| 7 |
Execution timed out |
2573 ms |
23180 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
