oj.uz

Submission #429629

# Submission time Handle Problem Language Result Execution time Memory
429629 2021-06-16T07:53:35 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
100 / 100
 4463 ms 49540 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;
vector<pii> S[404040];

void upd(int ind, int s, int e, int pos, pii x)
{
    S[ind].push_back(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 = lower_bound(S[ind].begin(), S[ind].end(), pii{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() > 10) 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});
    for(int i = 0; i < 404040; ++i) sort(S[i].begin(), S[i].end());

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9804 KB Output is correct
2 Correct 10 ms 9828 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct
4 Correct 8 ms 9824 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 8 ms 9804 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 8 ms 9808 KB Output is correct
9 Correct 9 ms 9932 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9804 KB Output is correct
2 Correct 10 ms 9828 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct
4 Correct 8 ms 9824 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 8 ms 9804 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 8 ms 9808 KB Output is correct
9 Correct 9 ms 9932 KB Output is correct
10 Correct 20 ms 10092 KB Output is correct
11 Correct 16 ms 10084 KB Output is correct
12 Correct 16 ms 10112 KB Output is correct
13 Correct 15 ms 10228 KB Output is correct
14 Correct 23 ms 10472 KB Output is correct
15 Correct 12 ms 10328 KB Output is correct
16 Correct 20 ms 10156 KB Output is correct
17 Correct 22 ms 10152 KB Output is correct
18 Correct 22 ms 10396 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9804 KB Output is correct
2 Correct 10 ms 9828 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct
4 Correct 8 ms 9824 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 8 ms 9804 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 8 ms 9808 KB Output is correct
9 Correct 9 ms 9932 KB Output is correct
10 Correct 20 ms 10092 KB Output is correct
11 Correct 16 ms 10084 KB Output is correct
12 Correct 16 ms 10112 KB Output is correct
13 Correct 15 ms 10228 KB Output is correct
14 Correct 23 ms 10472 KB Output is correct
15 Correct 12 ms 10328 KB Output is correct
16 Correct 20 ms 10156 KB Output is correct
17 Correct 22 ms 10152 KB Output is correct
18 Correct 22 ms 10396 KB Output is correct
19 Correct 4463 ms 33548 KB Output is correct
20 Correct 3214 ms 33808 KB Output is correct
21 Correct 1092 ms 32128 KB Output is correct
22 Correct 1137 ms 37368 KB Output is correct
23 Correct 2779 ms 49540 KB Output is correct
24 Correct 312 ms 43632 KB Output is correct
25 Correct 1905 ms 34808 KB Output is correct
26 Correct 3553 ms 35492 KB Output is correct
27 Correct 3156 ms 47048 KB Output is correct