oj.uz

답안 #97718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97718 2019-02-17T19:00:14 Z dalgerok 원 고르기 (APIO18_circle_selection) C++14
0 / 100
 1474 ms 83076 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;


const int N = 3e5 + 5;



int n, x[N], y[N], r[N], a[N];
int kill_[N], bound;

inline bool cmp(int xx, int yy){
    return r[xx] > r[yy] || (r[xx] == r[yy] && xx < yy);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(pair <int, int> x) const {
        static const uint64_t FIXED_RANDOM1 = chrono::steady_clock::now().time_since_epoch().count();
        static const uint64_t FIXED_RANDOM2 = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM1) ^ splitmix64(x.second + FIXED_RANDOM2);
    }
};
gp_hash_table < pair < int, int >, vector < int >, custom_hash > q;
inline void update(){
    q.clear();
    for(int i = 1; i <= n; i++){
        if(!kill_[i]){
            q[make_pair(x[i] / bound, y[i] / bound)].push_back(i);
        }
    }
}

inline bool intersect(int i, int j){
    return  1LL * (x[i] - x[j]) * (x[i] - x[j])
            +
            1LL * (y[i] - y[j]) * (y[i] - y[j])
            <=
            1LL * (r[i] + r[j]) * (r[i] + r[j]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
        a[i] = i;
    }
    sort(a + 1, a + n + 1, cmp);
    bound = 2e9 + 5;
    int pos = 1;
    while(true){
        while(pos <= n && kill_[a[pos]]){
            pos += 1;
        }
        if(pos == n + 1){
            break;
        }
        int cur = a[pos];
        if(2 * r[cur] <= bound){
            bound = r[cur];
            update();
        }
        kill_[cur] = cur;
        int xx = x[cur] / bound,
            yy = y[cur] / bound;
        for(int i = xx - 2; i <= xx + 2; i++){
            for(int j = yy - 2; j <= yy + 2; j++){
                if(q.find(make_pair(i, j)) != q.end()){
                    vector < int > nq;
                    for(auto it : q[make_pair(i, j)]){
                        cout << cur << " " << it << "\n";
                        if(intersect(cur, it)){
                            kill_[it] = cur;
                        }
                        else{
                            nq.push_back(it);
                        }
                    }
                    q[make_pair(i, j)] = nq;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << kill_[i] << " ";
    }
}
/**
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 266 ms 12504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1474 ms 83076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -