oj.uz

Submission #97715

# Submission time Handle Problem Language Result Execution time Memory
97715 2019-02-17T18:54:51 Z dalgerok Circle selection (APIO18_circle_selection) C++17
19 / 100
 3000 ms 44076 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 {
    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 (x.first + FIXED_RANDOM1) ^ (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)]){
                        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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 11 ms 1756 KB Output is correct
23 Correct 10 ms 1628 KB Output is correct
24 Correct 10 ms 1628 KB Output is correct
25 Correct 10 ms 1756 KB Output is correct
26 Correct 11 ms 1756 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 8540 KB Output is correct
2 Correct 184 ms 9120 KB Output is correct
3 Correct 182 ms 9704 KB Output is correct
4 Correct 185 ms 8416 KB Output is correct
5 Correct 476 ms 8940 KB Output is correct
6 Correct 552 ms 44012 KB Output is correct
7 Correct 1124 ms 11012 KB Output is correct
8 Correct 1072 ms 14852 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Execution timed out 3095 ms 20248 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 44076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 11 ms 1756 KB Output is correct
23 Correct 10 ms 1628 KB Output is correct
24 Correct 10 ms 1628 KB Output is correct
25 Correct 10 ms 1756 KB Output is correct
26 Correct 11 ms 1756 KB Output is correct
27 Correct 8 ms 640 KB Output is correct
28 Correct 12 ms 768 KB Output is correct
29 Correct 8 ms 768 KB Output is correct
30 Correct 22 ms 2968 KB Output is correct
31 Correct 21 ms 3016 KB Output is correct
32 Correct 23 ms 2968 KB Output is correct
33 Correct 76 ms 3544 KB Output is correct
34 Correct 65 ms 3544 KB Output is correct
35 Correct 103 ms 3040 KB Output is correct
36 Execution timed out 3016 ms 21448 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 11 ms 1756 KB Output is correct
23 Correct 10 ms 1628 KB Output is correct
24 Correct 10 ms 1628 KB Output is correct
25 Correct 10 ms 1756 KB Output is correct
26 Correct 11 ms 1756 KB Output is correct
27 Correct 181 ms 8540 KB Output is correct
28 Correct 184 ms 9120 KB Output is correct
29 Correct 182 ms 9704 KB Output is correct
30 Correct 185 ms 8416 KB Output is correct
31 Correct 476 ms 8940 KB Output is correct
32 Correct 552 ms 44012 KB Output is correct
33 Correct 1124 ms 11012 KB Output is correct
34 Correct 1072 ms 14852 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Execution timed out 3095 ms 20248 KB Time limit exceeded
37 Halted 0 ms 0 KB -