| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 429699 |
2021-06-16T08:48:14 Z |
송준혁(#7525) |
Power plants (CPSPC17_power) |
C++17 |
|
131 ms |
168768 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define HASH 7000003
#define INF (1ll<<61)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
int N, M, Q, num;
int chk[101010];
pii B[101010];
LL ans, X[101010], Y[101010];
vector<int> V[101010], ansX, ansY;
vector<pli> H[7070707];
int bid(LL x, LL k){
/*
int lo=0, hi=MOD, ret=0;
while (lo<=hi){
LL m=lo+hi>>1;
if (m*m <= 2*x*x/k) ret=m, lo=m+1;
else hi=m-1;
}
*/
return (int)sqrt(4*x*x/k);
}
inline int Hash(int x, int y){return (((LL)(x+5)*MOD + (y+5)) ^ 19059) % HASH;}
int id(int x, int y){
int t = Hash(x, y);
for (pli it : H[t]) if (it.fi == (LL)x*MOD+y) return it.se;
return -1;
}
bool dfs(int u, int c, LL k){
if (chk[u]) return chk[u]*c < 0;
chk[u] = c;
for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
if (dx*dy == 4 || dx*dy == -4) continue;
int t = id(B[u].fi+dx, B[u].se+dy);
if (t < 0) continue;
for (int v : V[t]){
if (v != u && (X[u]-X[v])*(X[u]-X[v])+(Y[u]-Y[v])*(Y[u]-Y[v]) <= k){
if (dfs(v, -c, k)) return true;
}
}
}
return false;
}
bool f(LL k){
for (int i=0; i<num; i++) V[i].clear();
for (int i=1; i<=N; i++) H[Hash(B[i].fi, B[i].se)].clear();
for (int i=1; i<=N; i++) chk[i] = 0;
num = 0;
for (int i=1; i<=N; i++){
B[i].fi = bid(X[i], k);
B[i].se = bid(Y[i], k);
if (id(B[i].fi, B[i].se) < 0){
H[Hash(B[i].fi, B[i].se)].pb(pli((LL)MOD*B[i].fi + B[i].se, num));
num++;
}
}
for (int i=1; i<=N; i++){
int t = id(B[i].fi, B[i].se);
V[t].pb(i);
if (V[t].size() > 2) return false;
}
for (int i=1; i<=N; i++){
if (chk[i]) continue;
if (dfs(i, 1, k)) return false;
}
return true;
}
int main(){
scanf("%d", &N);
for (int i=1; i<=N; i++) scanf("%lld %lld", &X[i], &Y[i]);
LL lo=0, hi=INF;
while (lo<=hi){
LL m = lo+hi>>1;
if (f(m)) ans = m, lo = m + 1;
else hi = m - 1;
}
printf("%lld\n", ans+1);
f(ans);
for (int i=1; i<=N; i++){
if (chk[i] > 0) ansX.pb(i);
else ansY.pb(i);
}
printf("%d\n", ansX.size());
for (int x : ansX) printf("%d ", x);
printf("\n");
printf("%d\n", ansY.size());
for (int x : ansY) printf("%d ", x);
printf("\n");
return 0;
}
Compilation message
Main.cpp: In function 'bool dfs(int, int, LL)':
Main.cpp:47:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
47 | for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
| ^~
Main.cpp:47:58: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
47 | for (register int dx=-2; dx<=2; dx++) for (register int dy=-2; dy<=2; dy++){
| ^~
Main.cpp: In function 'int main()':
Main.cpp:90:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | LL m = lo+hi>>1;
| ~~^~~
Main.cpp:100:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
100 | printf("%d\n", ansX.size());
| ~^ ~~~~~~~~~~~
| | |
| int std::vector<int>::size_type {aka long unsigned int}
| %ld
Main.cpp:103:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
103 | printf("%d\n", ansY.size());
| ~^ ~~~~~~~~~~~
| | |
| int std::vector<int>::size_type {aka long unsigned int}
| %ld
Main.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
Main.cpp:87:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | for (int i=1; i<=N; i++) scanf("%lld %lld", &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
168728 KB |
Output is correct |
| 2 |
Correct |
120 ms |
168768 KB |
Output is correct |
| 3 |
Correct |
114 ms |
168732 KB |
Output is correct |
| 4 |
Incorrect |
118 ms |
168648 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
168728 KB |
Output is correct |
| 2 |
Correct |
120 ms |
168768 KB |
Output is correct |
| 3 |
Correct |
114 ms |
168732 KB |
Output is correct |
| 4 |
Incorrect |
118 ms |
168648 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
168728 KB |
Output is correct |
| 2 |
Correct |
120 ms |
168768 KB |
Output is correct |
| 3 |
Correct |
114 ms |
168732 KB |
Output is correct |
| 4 |
Incorrect |
118 ms |
168648 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
