oj.uz

Submission #430105

# Submission time Handle Problem Language Result Execution time Memory
430105 2021-06-16T11:30:12 Z 최서현(#7488) Power plants (CPSPC17_power) C++17
100 / 100
 5266 ms 49416 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 9 ms 9824 KB Output is correct
3 Correct 10 ms 9804 KB Output is correct
4 Correct 8 ms 9804 KB Output is correct
5 Correct 10 ms 9804 KB Output is correct
6 Correct 9 ms 9820 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 10 ms 9804 KB Output is correct
9 Correct 9 ms 9808 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 9 ms 9824 KB Output is correct
3 Correct 10 ms 9804 KB Output is correct
4 Correct 8 ms 9804 KB Output is correct
5 Correct 10 ms 9804 KB Output is correct
6 Correct 9 ms 9820 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 10 ms 9804 KB Output is correct
9 Correct 9 ms 9808 KB Output is correct
10 Correct 21 ms 10084 KB Output is correct
11 Correct 17 ms 10060 KB Output is correct
12 Correct 17 ms 10116 KB Output is correct
13 Correct 16 ms 10260 KB Output is correct
14 Correct 27 ms 10476 KB Output is correct
15 Correct 15 ms 10328 KB Output is correct
16 Correct 21 ms 10168 KB Output is correct
17 Correct 28 ms 10168 KB Output is correct
18 Correct 22 ms 10440 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 9 ms 9824 KB Output is correct
3 Correct 10 ms 9804 KB Output is correct
4 Correct 8 ms 9804 KB Output is correct
5 Correct 10 ms 9804 KB Output is correct
6 Correct 9 ms 9820 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 10 ms 9804 KB Output is correct
9 Correct 9 ms 9808 KB Output is correct
10 Correct 21 ms 10084 KB Output is correct
11 Correct 17 ms 10060 KB Output is correct
12 Correct 17 ms 10116 KB Output is correct
13 Correct 16 ms 10260 KB Output is correct
14 Correct 27 ms 10476 KB Output is correct
15 Correct 15 ms 10328 KB Output is correct
16 Correct 21 ms 10168 KB Output is correct
17 Correct 28 ms 10168 KB Output is correct
18 Correct 22 ms 10440 KB Output is correct
19 Correct 5266 ms 35028 KB Output is correct
20 Correct 3804 ms 33804 KB Output is correct
21 Correct 1292 ms 32176 KB Output is correct
22 Correct 1257 ms 37368 KB Output is correct
23 Correct 3267 ms 49416 KB Output is correct
24 Correct 289 ms 43552 KB Output is correct
25 Correct 2191 ms 34760 KB Output is correct
26 Correct 4350 ms 35476 KB Output is correct
27 Correct 3370 ms 47024 KB Output is correct