| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 429623 |
2021-06-16T07:51:01 Z |
최서현(#7502) |
Power plants (CPSPC17_power) |
C++17 |
|
6000 ms |
104760 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int INF = (int)1e9 + 7;
int n, N;
pii A[101010];
int col[101010];
vector<int> pr;
set<pii> S[404040];
void upd(int ind, int s, int e, int pos, pii x)
{
S[ind].insert(x);
if(s + 1 == e) return;
int mid = s + e >> 1;
if(pos < mid) upd(ind << 1, s, mid, pos, x);
else upd(ind << 1 | 1, mid, e, pos, x);
}
void qry(vector<int> &ret, int ind, int s, int e, int l, int r, int xl, int xr)
{
if(e <= l || r <= s) return;
if(l <= s && e <= r)
{
auto it = S[ind].lower_bound({xl, -1});
while(it != S[ind].end() && it->ff <= xr) ret.push_back(it->ss), ++it;
return;
}
int mid = s + e >> 1;
qry(ret, ind << 1, s, mid, l, r, xl, xr);
qry(ret, ind << 1 | 1, mid, e, l, r, xl, xr);
}
bool dfs(int x, int t, long long d, int c)
{
if(col[x] == c) return true;
if(col[x] == 3 - c) return false;
col[x] = c;
vector<int> ret;
qry(ret, 1, 0, N, lower_bound(pr.begin(), pr.end(), (A[x].ff < t ? -1 : A[x].ff - t)) - pr.begin(),
upper_bound(pr.begin(), pr.end(), (A[x].ff > INF - t ? INF : A[x].ff + t))
- pr.begin(), (A[x].ss < t ? -1 : A[x].ss - t), (A[x].ss > INF - t ? INF : A[x].ss + t));
if(ret.size() > 25) return false;
for(auto i : ret) if(i != x && 1ll * (A[i].ff - A[x].ff) * (A[i].ff - A[x].ff) + 1ll * (A[i].ss - A[x].ss) * (A[i].ss - A[x].ss) <= d)
{
if(!dfs(i, t, d, 3 - c)) return false;
}
return true;
}
int mysqrt(long long x)
{
int s = 0, e = (int)2e9;
while(s + 1 < e)
{
int mid = 1ll * s + e >> 1;
if(1ll * mid * mid <= x) s = mid;
else e = mid;
}
return s;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n; ++i) cin >> A[i].ff >> A[i].ss;
for(int i = 0; i < n; ++i) pr.push_back(A[i].ff);
sort(pr.begin(), pr.end());
pr.resize(unique(pr.begin(), pr.end()) - pr.begin());
N = pr.size();
for(int i = 0; i < n; ++i) upd(1, 0, N, lower_bound(pr.begin(), pr.end(), A[i].ff) - pr.begin(), {A[i].ss, i});
long long s = 0, e = (long long)2e18 + 100;
while(s + 1 < e)
{
long long mid = s + e >> 1;
int t = mysqrt(mid);
for(int i = 0; i < n; ++i) col[i] = 0;
bool flag = true;
for(int i = 0; i < n; ++i) if(!col[i])
{
if(!dfs(i, t, mid, 1)) {flag = false; break;}
}
if(flag) s = mid;
else e = mid;
}
for(int i = 0; i < n; ++i) col[i] = 0;
int t = mysqrt(s);
for(int i = 0; i < n; ++i) if(!col[i]) dfs(i, t, s, 1);
vector<int> A, B;
for(int i = 0; i < n; ++i)
{
if(col[i] == 1) A.push_back(i);
else B.push_back(i);
}
cout << e << '\n';
cout << A.size() << '\n';
for(auto i : A) cout << i + 1 << ' '; cout << '\n';
cout << B.size() << '\n';
for(auto i : B) cout << i + 1 << ' '; cout << '\n';
}
Compilation message
Main.cpp: In function 'void upd(int, int, int, int, std::pair<int, int>)':
Main.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'void qry(std::vector<int>&, int, int, int, int, int, int, int)':
Main.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'int mysqrt(long long int)':
Main.cpp:65:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = 1ll * s + e >> 1;
| ~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:88:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | long long mid = s + e >> 1;
| ~~^~~
Main.cpp:113:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
113 | for(auto i : A) cout << i + 1 << ' '; cout << '\n';
| ^~~
Main.cpp:113:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
113 | for(auto i : A) cout << i + 1 << ' '; cout << '\n';
| ^~~~
Main.cpp:115:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
115 | for(auto i : B) cout << i + 1 << ' '; cout << '\n';
| ^~~
Main.cpp:115:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
115 | for(auto i : B) cout << i + 1 << ' '; cout << '\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19276 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 3 |
Correct |
11 ms |
19336 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 5 |
Correct |
12 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
13 ms |
19276 KB |
Output is correct |
| 7 |
Correct |
11 ms |
19244 KB |
Output is correct |
| 8 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 9 |
Correct |
14 ms |
19276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19276 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 3 |
Correct |
11 ms |
19336 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 5 |
Correct |
12 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
13 ms |
19276 KB |
Output is correct |
| 7 |
Correct |
11 ms |
19244 KB |
Output is correct |
| 8 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 9 |
Correct |
14 ms |
19276 KB |
Output is correct |
| 10 |
Correct |
32 ms |
20472 KB |
Output is correct |
| 11 |
Correct |
29 ms |
20336 KB |
Output is correct |
| 12 |
Correct |
28 ms |
20336 KB |
Output is correct |
| 13 |
Correct |
29 ms |
20492 KB |
Output is correct |
| 14 |
Correct |
33 ms |
20664 KB |
Output is correct |
| 15 |
Correct |
20 ms |
20336 KB |
Output is correct |
| 16 |
Correct |
35 ms |
20456 KB |
Output is correct |
| 17 |
Correct |
41 ms |
20428 KB |
Output is correct |
| 18 |
Correct |
31 ms |
20760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19276 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 3 |
Correct |
11 ms |
19336 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 5 |
Correct |
12 ms |
19288 KB |
Output is correct |
| 6 |
Correct |
13 ms |
19276 KB |
Output is correct |
| 7 |
Correct |
11 ms |
19244 KB |
Output is correct |
| 8 |
Correct |
11 ms |
19276 KB |
Output is correct |
| 9 |
Correct |
14 ms |
19276 KB |
Output is correct |
| 10 |
Correct |
32 ms |
20472 KB |
Output is correct |
| 11 |
Correct |
29 ms |
20336 KB |
Output is correct |
| 12 |
Correct |
28 ms |
20336 KB |
Output is correct |
| 13 |
Correct |
29 ms |
20492 KB |
Output is correct |
| 14 |
Correct |
33 ms |
20664 KB |
Output is correct |
| 15 |
Correct |
20 ms |
20336 KB |
Output is correct |
| 16 |
Correct |
35 ms |
20456 KB |
Output is correct |
| 17 |
Correct |
41 ms |
20428 KB |
Output is correct |
| 18 |
Correct |
31 ms |
20760 KB |
Output is correct |
| 19 |
Execution timed out |
6103 ms |
104760 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
