oj.uz

답안 #429616

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

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 13 ms 19276 KB Output is correct
2 Correct 12 ms 19272 KB Output is correct
3 Correct 13 ms 19276 KB Output is correct
4 Correct 15 ms 19444 KB Output is correct
5 Correct 15 ms 19276 KB Output is correct
6 Correct 13 ms 19220 KB Output is correct
7 Correct 12 ms 19228 KB Output is correct
8 Correct 12 ms 19276 KB Output is correct
9 Correct 15 ms 19332 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19276 KB Output is correct
2 Correct 12 ms 19272 KB Output is correct
3 Correct 13 ms 19276 KB Output is correct
4 Correct 15 ms 19444 KB Output is correct
5 Correct 15 ms 19276 KB Output is correct
6 Correct 13 ms 19220 KB Output is correct
7 Correct 12 ms 19228 KB Output is correct
8 Correct 12 ms 19276 KB Output is correct
9 Correct 15 ms 19332 KB Output is correct
10 Correct 29 ms 20464 KB Output is correct
11 Correct 26 ms 20348 KB Output is correct
12 Correct 22 ms 20344 KB Output is correct
13 Correct 24 ms 20556 KB Output is correct
14 Correct 40 ms 20656 KB Output is correct
15 Correct 24 ms 20272 KB Output is correct
16 Correct 29 ms 20512 KB Output is correct
17 Correct 31 ms 20428 KB Output is correct
18 Correct 28 ms 20648 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19276 KB Output is correct
2 Correct 12 ms 19272 KB Output is correct
3 Correct 13 ms 19276 KB Output is correct
4 Correct 15 ms 19444 KB Output is correct
5 Correct 15 ms 19276 KB Output is correct
6 Correct 13 ms 19220 KB Output is correct
7 Correct 12 ms 19228 KB Output is correct
8 Correct 12 ms 19276 KB Output is correct
9 Correct 15 ms 19332 KB Output is correct
10 Correct 29 ms 20464 KB Output is correct
11 Correct 26 ms 20348 KB Output is correct
12 Correct 22 ms 20344 KB Output is correct
13 Correct 24 ms 20556 KB Output is correct
14 Correct 40 ms 20656 KB Output is correct
15 Correct 24 ms 20272 KB Output is correct
16 Correct 29 ms 20512 KB Output is correct
17 Correct 31 ms 20428 KB Output is correct
18 Correct 28 ms 20648 KB Output is correct
19 Execution timed out 6028 ms 104676 KB Time limit exceeded
20 Halted 0 ms 0 KB -