oj.uz

Submission #364613

# Submission time Handle Problem Language Result Execution time Memory
364613 2021-02-09T14:36:05 Z doowey Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 638268 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
ll cut = (1ll << 31);
int sol[N];
ll xi[N];
ll yi[N];
ll ri[N];

ll sq(ll v){
    return v * 1ll * v;
}

bool check(int i, int j){
    // sqrt((xi-xj)^2+(yi-yj)^2) <= (ri + rj)
    ll val = sq(xi[i] - xi[j]) + sq(yi[i] - yi[j]);
    ll cmp = sq(ri[i] + ri[j]);
    if(val <= cmp)
        return true;
    return false;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<pii> cir;
    for(int i = 1; i <= n; i ++ ){
        cin >> xi[i] >> yi[i] >> ri[i];
        cir.push_back({ri[i], -i});
    }
    sort(cir.begin(), cir.end());
    int id;
    bool has;
    map<pii, set<int>> idk;
    ll ci, cj;
    for(int i = cir.size() - 1; i >= 0 ;i -- ){
        id = -cir[i].se;
        if(sol[id] == 0){
            has=false;
            while(cut/2ll >= ri[id]){
                has=true;
                cut /= 2ll;
            }

            if(has){
                idk.clear();
                for(int j =  1; j <= n; j ++ ){
                    if(sol[j] == 0){
                        idk[mp(xi[j]/cut,yi[j]/cut)].insert(j);
                    }
                }
            }
            ci = xi[id]/cut;
            cj = yi[id]/cut;
            vector<int> del;
            for(ll p = -2; p <= 2; p ++ ){
                for(ll q = -2 ; q <= 2; q ++ ){
                    for(auto v : idk[mp(ci + p, cj + q)]){
                        if(check(id,v)){
                            del.push_back(v);
                        }
                    }
                }
            }
            for(auto x : del){
                sol[x]=id;
                idk[mp(xi[x]/cut,yi[x]/cut)].erase(x);
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << sol[i] << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 4 ms 1132 KB Output is correct
20 Correct 5 ms 1132 KB Output is correct
21 Correct 5 ms 1004 KB Output is correct
22 Correct 41 ms 7020 KB Output is correct
23 Correct 46 ms 7404 KB Output is correct
24 Correct 42 ms 5868 KB Output is correct
25 Correct 40 ms 6764 KB Output is correct
26 Correct 43 ms 7148 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 39504 KB Output is correct
2 Correct 288 ms 37840 KB Output is correct
3 Correct 273 ms 37968 KB Output is correct
4 Correct 274 ms 39564 KB Output is correct
5 Correct 541 ms 35408 KB Output is correct
6 Correct 1578 ms 97592 KB Output is correct
7 Correct 699 ms 37344 KB Output is correct
8 Correct 820 ms 47440 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1684 ms 125984 KB Output is correct
3 Execution timed out 3086 ms 342184 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 4 ms 1132 KB Output is correct
20 Correct 5 ms 1132 KB Output is correct
21 Correct 5 ms 1004 KB Output is correct
22 Correct 41 ms 7020 KB Output is correct
23 Correct 46 ms 7404 KB Output is correct
24 Correct 42 ms 5868 KB Output is correct
25 Correct 40 ms 6764 KB Output is correct
26 Correct 43 ms 7148 KB Output is correct
27 Correct 9 ms 1776 KB Output is correct
28 Correct 9 ms 1776 KB Output is correct
29 Correct 8 ms 1776 KB Output is correct
30 Correct 102 ms 15344 KB Output is correct
31 Correct 93 ms 15088 KB Output is correct
32 Correct 107 ms 11504 KB Output is correct
33 Correct 89 ms 14052 KB Output is correct
34 Correct 93 ms 14080 KB Output is correct
35 Correct 96 ms 13796 KB Output is correct
36 Correct 1453 ms 137188 KB Output is correct
37 Correct 1439 ms 121060 KB Output is correct
38 Correct 1500 ms 139108 KB Output is correct
39 Correct 943 ms 45240 KB Output is correct
40 Correct 960 ms 45284 KB Output is correct
41 Correct 946 ms 45248 KB Output is correct
42 Correct 320 ms 18336 KB Output is correct
43 Correct 1012 ms 250596 KB Output is correct
44 Correct 1028 ms 250852 KB Output is correct
45 Correct 1020 ms 250628 KB Output is correct
46 Correct 1031 ms 250988 KB Output is correct
47 Correct 1025 ms 251108 KB Output is correct
48 Correct 1020 ms 251156 KB Output is correct
49 Correct 1012 ms 251240 KB Output is correct
50 Correct 1004 ms 250852 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 4 ms 1132 KB Output is correct
20 Correct 5 ms 1132 KB Output is correct
21 Correct 5 ms 1004 KB Output is correct
22 Correct 41 ms 7020 KB Output is correct
23 Correct 46 ms 7404 KB Output is correct
24 Correct 42 ms 5868 KB Output is correct
25 Correct 40 ms 6764 KB Output is correct
26 Correct 43 ms 7148 KB Output is correct
27 Correct 278 ms 39504 KB Output is correct
28 Correct 288 ms 37840 KB Output is correct
29 Correct 273 ms 37968 KB Output is correct
30 Correct 274 ms 39564 KB Output is correct
31 Correct 541 ms 35408 KB Output is correct
32 Correct 1578 ms 97592 KB Output is correct
33 Correct 699 ms 37344 KB Output is correct
34 Correct 820 ms 47440 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1684 ms 125984 KB Output is correct
37 Execution timed out 3086 ms 342184 KB Time limit exceeded
38 Halted 0 ms 0 KB -