oj.uz

Submission #429592

# Submission time Handle Problem Language Result Execution time Memory
429592 2021-06-16T07:30:03 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 137080 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() > 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 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19276 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 19272 KB Output is correct
5 Correct 14 ms 19276 KB Output is correct
6 Correct 12 ms 19324 KB Output is correct
7 Correct 12 ms 19276 KB Output is correct
8 Correct 12 ms 19276 KB Output is correct
9 Correct 12 ms 19276 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19276 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 19272 KB Output is correct
5 Correct 14 ms 19276 KB Output is correct
6 Correct 12 ms 19324 KB Output is correct
7 Correct 12 ms 19276 KB Output is correct
8 Correct 12 ms 19276 KB Output is correct
9 Correct 12 ms 19276 KB Output is correct
10 Correct 38 ms 20940 KB Output is correct
11 Correct 35 ms 20732 KB Output is correct
12 Correct 32 ms 20768 KB Output is correct
13 Correct 34 ms 20884 KB Output is correct
14 Correct 46 ms 21328 KB Output is correct
15 Correct 30 ms 20940 KB Output is correct
16 Correct 35 ms 20936 KB Output is correct
17 Correct 39 ms 20940 KB Output is correct
18 Correct 35 ms 21204 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19276 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 19272 KB Output is correct
5 Correct 14 ms 19276 KB Output is correct
6 Correct 12 ms 19324 KB Output is correct
7 Correct 12 ms 19276 KB Output is correct
8 Correct 12 ms 19276 KB Output is correct
9 Correct 12 ms 19276 KB Output is correct
10 Correct 38 ms 20940 KB Output is correct
11 Correct 35 ms 20732 KB Output is correct
12 Correct 32 ms 20768 KB Output is correct
13 Correct 34 ms 20884 KB Output is correct
14 Correct 46 ms 21328 KB Output is correct
15 Correct 30 ms 20940 KB Output is correct
16 Correct 35 ms 20936 KB Output is correct
17 Correct 39 ms 20940 KB Output is correct
18 Correct 35 ms 21204 KB Output is correct
19 Execution timed out 6014 ms 137080 KB Time limit exceeded
20 Halted 0 ms 0 KB -