oj.uz

답안 #429623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429623 2021-06-16T07:51:01 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 104760 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;
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 ? -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() > 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 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});

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19276 KB Output is correct
2 Correct 11 ms 19276 KB Output is correct
3 Correct 11 ms 19336 KB Output is correct
4 Correct 11 ms 19276 KB Output is correct
5 Correct 12 ms 19288 KB Output is correct
6 Correct 13 ms 19276 KB Output is correct
7 Correct 11 ms 19244 KB Output is correct
8 Correct 11 ms 19276 KB Output is correct
9 Correct 14 ms 19276 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19276 KB Output is correct
2 Correct 11 ms 19276 KB Output is correct
3 Correct 11 ms 19336 KB Output is correct
4 Correct 11 ms 19276 KB Output is correct
5 Correct 12 ms 19288 KB Output is correct
6 Correct 13 ms 19276 KB Output is correct
7 Correct 11 ms 19244 KB Output is correct
8 Correct 11 ms 19276 KB Output is correct
9 Correct 14 ms 19276 KB Output is correct
10 Correct 32 ms 20472 KB Output is correct
11 Correct 29 ms 20336 KB Output is correct
12 Correct 28 ms 20336 KB Output is correct
13 Correct 29 ms 20492 KB Output is correct
14 Correct 33 ms 20664 KB Output is correct
15 Correct 20 ms 20336 KB Output is correct
16 Correct 35 ms 20456 KB Output is correct
17 Correct 41 ms 20428 KB Output is correct
18 Correct 31 ms 20760 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19276 KB Output is correct
2 Correct 11 ms 19276 KB Output is correct
3 Correct 11 ms 19336 KB Output is correct
4 Correct 11 ms 19276 KB Output is correct
5 Correct 12 ms 19288 KB Output is correct
6 Correct 13 ms 19276 KB Output is correct
7 Correct 11 ms 19244 KB Output is correct
8 Correct 11 ms 19276 KB Output is correct
9 Correct 14 ms 19276 KB Output is correct
10 Correct 32 ms 20472 KB Output is correct
11 Correct 29 ms 20336 KB Output is correct
12 Correct 28 ms 20336 KB Output is correct
13 Correct 29 ms 20492 KB Output is correct
14 Correct 33 ms 20664 KB Output is correct
15 Correct 20 ms 20336 KB Output is correct
16 Correct 35 ms 20456 KB Output is correct
17 Correct 41 ms 20428 KB Output is correct
18 Correct 31 ms 20760 KB Output is correct
19 Execution timed out 6103 ms 104760 KB Time limit exceeded
20 Halted 0 ms 0 KB -