oj.uz

답안 #429598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429598 2021-06-16T07:33:34 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
0 / 100
 15 ms 19344 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(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) - 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() > 16) 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 e;
}

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 = 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 = (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 'long long int mysqrt(long long int)':
Main.cpp:64:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = 1ll * s + e >> 1;
      |                   ~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:87:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         long long mid = s + e >> 1;
      |                         ~~^~~
Main.cpp:112:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  112 |     for(auto i : A) cout << i + 1 << ' '; cout << '\n';
      |     ^~~
Main.cpp:112:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  112 |     for(auto i : A) cout << i + 1 << ' '; cout << '\n';
      |                                           ^~~~
Main.cpp:114:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  114 |     for(auto i : B) cout << i + 1 << ' '; cout << '\n';
      |     ^~~
Main.cpp:114:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  114 |     for(auto i : B) cout << i + 1 << ' '; cout << '\n';
      |                                           ^~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19272 KB Output is correct
2 Correct 15 ms 19276 KB Output is correct
3 Correct 12 ms 19276 KB Output is correct
4 Correct 12 ms 19344 KB Output is correct
5 Correct 13 ms 19276 KB Output is correct
6 Incorrect 12 ms 19276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19272 KB Output is correct
2 Correct 15 ms 19276 KB Output is correct
3 Correct 12 ms 19276 KB Output is correct
4 Correct 12 ms 19344 KB Output is correct
5 Correct 13 ms 19276 KB Output is correct
6 Incorrect 12 ms 19276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19272 KB Output is correct
2 Correct 15 ms 19276 KB Output is correct
3 Correct 12 ms 19276 KB Output is correct
4 Correct 12 ms 19344 KB Output is correct
5 Correct 13 ms 19276 KB Output is correct
6 Incorrect 12 ms 19276 KB Output isn't correct
7 Halted 0 ms 0 KB -