| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 429567 |
2021-06-16T06:50:54 Z |
최서현(#7502) |
Power plants (CPSPC17_power) |
C++17 |
|
14 ms |
19308 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#define pii pair<int, int>
#define ff first
#define ss second
#define int long long
using namespace std;
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(mid < pos) 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) - pr.begin(),
upper_bound(pr.begin(), pr.end(), A[x].ff + t) - pr.begin(), A[x].ss - t, 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;
}
signed 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 = (int)sqrt(mid) + 1;
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 = (int)sqrt(s) + 1;
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(long long int, long long int, long long int, long long int, std::pair<long long int, long long 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<long long int>&, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:75:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | long long mid = s + e >> 1;
| ~~^~~
Main.cpp:100:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
100 | for(auto i : A) cout << i + 1 << ' '; cout << '\n';
| ^~~
Main.cpp:100:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
100 | for(auto i : A) cout << i + 1 << ' '; cout << '\n';
| ^~~~
Main.cpp:102:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
102 | for(auto i : B) cout << i + 1 << ' '; cout << '\n';
| ^~~
Main.cpp:102:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
102 | for(auto i : B) cout << i + 1 << ' '; cout << '\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
