oj.uz

답안 #429594

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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19288 KB Output is correct
2 Correct 12 ms 19276 KB Output is correct
3 Correct 12 ms 19348 KB Output is correct
4 Correct 13 ms 19348 KB Output is correct
5 Correct 12 ms 19344 KB Output is correct
6 Correct 13 ms 19276 KB Output is correct
7 Correct 13 ms 19280 KB Output is correct
8 Correct 13 ms 19272 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 19288 KB Output is correct
2 Correct 12 ms 19276 KB Output is correct
3 Correct 12 ms 19348 KB Output is correct
4 Correct 13 ms 19348 KB Output is correct
5 Correct 12 ms 19344 KB Output is correct
6 Correct 13 ms 19276 KB Output is correct
7 Correct 13 ms 19280 KB Output is correct
8 Correct 13 ms 19272 KB Output is correct
9 Correct 14 ms 19276 KB Output is correct
10 Correct 33 ms 20820 KB Output is correct
11 Correct 29 ms 20744 KB Output is correct
12 Correct 26 ms 20716 KB Output is correct
13 Correct 26 ms 20840 KB Output is correct
14 Correct 35 ms 21192 KB Output is correct
15 Correct 23 ms 20860 KB Output is correct
16 Correct 38 ms 20880 KB Output is correct
17 Correct 42 ms 20812 KB Output is correct
18 Correct 37 ms 21088 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19288 KB Output is correct
2 Correct 12 ms 19276 KB Output is correct
3 Correct 12 ms 19348 KB Output is correct
4 Correct 13 ms 19348 KB Output is correct
5 Correct 12 ms 19344 KB Output is correct
6 Correct 13 ms 19276 KB Output is correct
7 Correct 13 ms 19280 KB Output is correct
8 Correct 13 ms 19272 KB Output is correct
9 Correct 14 ms 19276 KB Output is correct
10 Correct 33 ms 20820 KB Output is correct
11 Correct 29 ms 20744 KB Output is correct
12 Correct 26 ms 20716 KB Output is correct
13 Correct 26 ms 20840 KB Output is correct
14 Correct 35 ms 21192 KB Output is correct
15 Correct 23 ms 20860 KB Output is correct
16 Correct 38 ms 20880 KB Output is correct
17 Correct 42 ms 20812 KB Output is correct
18 Correct 37 ms 21088 KB Output is correct
19 Execution timed out 6052 ms 134904 KB Time limit exceeded
20 Halted 0 ms 0 KB -