oj.uz

Submission #407459

# Submission time Handle Problem Language Result Execution time Memory
407459 2021-05-19T01:27:43 Z RGBB Circle selection (APIO18_circle_selection) C++14
100 / 100
 2667 ms 388484 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int>pp;
const int MAXN=300000;
bool vis[MAXN];
int n,cr,outp[MAXN],inp[MAXN][3];
pp take[MAXN];
gp_hash_table<int,gp_hash_table<int,vector<int>>>plane;
void initialize(int cx,int cy){
    if(plane.find(cx)==plane.end()){
        gp_hash_table<int,vector<int>>temp;
        plane[cx]=temp;
    }
    if(plane[cx].find(cy)==plane[cx].end()){
        vector<int>temp;
        plane[cx][cy]=temp;
    }
}
void create(){
    plane.clear();
    for(pp i:take){
        if(vis[i.second])continue;
        int cx=(inp[i.second][0]>>cr);
        int cy=(inp[i.second][1]>>cr);
        initialize(cx,cy);
        plane[cx][cy].push_back(i.second);
    }
}
ll xx,yy,rr;
bool intersect(int a,int b){
    xx=inp[a][0]-inp[b][0];
    yy=inp[a][1]-inp[b][1];
    rr=inp[a][2]+inp[b][2];
    if(xx*xx+yy*yy<=rr*rr)return true;
    return false;
}
void calc(int c){
    int cx=(inp[c][0]>>cr);
    int cy=(inp[c][1]>>cr);
    for(int i=-1;i<=1;i++){
        for(int y=-1;y<=1;y++){
            if(plane.find(cx+i)==plane.end()||plane[cx+i].find(cy+y)==plane[cx+i].end())continue;
            for(int i:plane[cx+i][cy+y]){
                if(!vis[i]&&intersect(i,c)){
                    outp[i]=c;
                    vis[i]=true;
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(vis,false,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>inp[i][0]>>inp[i][1]>>inp[i][2];
        take[i]={-inp[i][2],i};
    }
    sort(take,take+n);
    cr=30;
    create();
    bool change=false;
    for(int i=0;i<n;i++){
        if(vis[take[i].second])continue;
        while(-take[i].first<(double)(1<<(cr-2))/sqrt(2)){
            cr--;
            change=true;
        }
        if(change)create();
        change=false;
        calc(take[i].second);
    }
    for(int i=0;i<n-1;i++)cout<<outp[i]+1<<" ";
    cout<<outp[n-1]+1<<"\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3840 KB Output is correct
2 Correct 28 ms 3844 KB Output is correct
3 Correct 15 ms 2804 KB Output is correct
4 Correct 41 ms 3832 KB Output is correct
5 Correct 14 ms 2792 KB Output is correct
6 Correct 16 ms 2756 KB Output is correct
7 Correct 14 ms 2776 KB Output is correct
8 Correct 16 ms 2784 KB Output is correct
9 Correct 41 ms 3872 KB Output is correct
10 Correct 15 ms 2736 KB Output is correct
11 Correct 127 ms 3868 KB Output is correct
12 Correct 34 ms 3840 KB Output is correct
13 Correct 41 ms 3884 KB Output is correct
14 Correct 43 ms 3916 KB Output is correct
15 Correct 61 ms 3876 KB Output is correct
16 Correct 17 ms 2852 KB Output is correct
17 Correct 28 ms 3876 KB Output is correct
18 Correct 15 ms 2884 KB Output is correct
19 Correct 19 ms 3068 KB Output is correct
20 Correct 18 ms 3044 KB Output is correct
21 Correct 22 ms 2988 KB Output is correct
22 Correct 74 ms 5440 KB Output is correct
23 Correct 64 ms 4912 KB Output is correct
24 Correct 96 ms 5632 KB Output is correct
25 Correct 84 ms 8908 KB Output is correct
26 Correct 58 ms 6464 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 16588 KB Output is correct
2 Correct 214 ms 16564 KB Output is correct
3 Correct 230 ms 17928 KB Output is correct
4 Correct 212 ms 17288 KB Output is correct
5 Correct 261 ms 16772 KB Output is correct
6 Correct 747 ms 61692 KB Output is correct
7 Correct 304 ms 22180 KB Output is correct
8 Correct 388 ms 26068 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3784 KB Output is correct
2 Correct 327 ms 21812 KB Output is correct
3 Correct 1352 ms 67364 KB Output is correct
4 Correct 1378 ms 67468 KB Output is correct
5 Correct 1006 ms 46152 KB Output is correct
6 Correct 394 ms 23736 KB Output is correct
7 Correct 180 ms 14740 KB Output is correct
8 Correct 93 ms 9656 KB Output is correct
9 Correct 1452 ms 57208 KB Output is correct
10 Correct 827 ms 37800 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 73784 KB Output is correct
2 Correct 1255 ms 387084 KB Output is correct
3 Correct 284 ms 20188 KB Output is correct
4 Correct 998 ms 203248 KB Output is correct
5 Correct 1069 ms 204696 KB Output is correct
6 Correct 263 ms 19728 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3840 KB Output is correct
2 Correct 28 ms 3844 KB Output is correct
3 Correct 15 ms 2804 KB Output is correct
4 Correct 41 ms 3832 KB Output is correct
5 Correct 14 ms 2792 KB Output is correct
6 Correct 16 ms 2756 KB Output is correct
7 Correct 14 ms 2776 KB Output is correct
8 Correct 16 ms 2784 KB Output is correct
9 Correct 41 ms 3872 KB Output is correct
10 Correct 15 ms 2736 KB Output is correct
11 Correct 127 ms 3868 KB Output is correct
12 Correct 34 ms 3840 KB Output is correct
13 Correct 41 ms 3884 KB Output is correct
14 Correct 43 ms 3916 KB Output is correct
15 Correct 61 ms 3876 KB Output is correct
16 Correct 17 ms 2852 KB Output is correct
17 Correct 28 ms 3876 KB Output is correct
18 Correct 15 ms 2884 KB Output is correct
19 Correct 19 ms 3068 KB Output is correct
20 Correct 18 ms 3044 KB Output is correct
21 Correct 22 ms 2988 KB Output is correct
22 Correct 74 ms 5440 KB Output is correct
23 Correct 64 ms 4912 KB Output is correct
24 Correct 96 ms 5632 KB Output is correct
25 Correct 84 ms 8908 KB Output is correct
26 Correct 58 ms 6464 KB Output is correct
27 Correct 22 ms 3264 KB Output is correct
28 Correct 20 ms 3236 KB Output is correct
29 Correct 22 ms 3216 KB Output is correct
30 Correct 66 ms 6068 KB Output is correct
31 Correct 72 ms 7224 KB Output is correct
32 Correct 89 ms 7192 KB Output is correct
33 Correct 73 ms 7924 KB Output is correct
34 Correct 73 ms 7936 KB Output is correct
35 Correct 95 ms 8948 KB Output is correct
36 Correct 399 ms 29868 KB Output is correct
37 Correct 409 ms 29816 KB Output is correct
38 Correct 405 ms 29804 KB Output is correct
39 Correct 459 ms 9844 KB Output is correct
40 Correct 448 ms 9792 KB Output is correct
41 Correct 477 ms 9856 KB Output is correct
42 Correct 126 ms 8452 KB Output is correct
43 Correct 374 ms 98644 KB Output is correct
44 Correct 421 ms 98664 KB Output is correct
45 Correct 416 ms 98688 KB Output is correct
46 Correct 401 ms 98616 KB Output is correct
47 Correct 421 ms 98608 KB Output is correct
48 Correct 405 ms 98684 KB Output is correct
49 Correct 404 ms 98648 KB Output is correct
50 Correct 414 ms 98608 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3840 KB Output is correct
2 Correct 28 ms 3844 KB Output is correct
3 Correct 15 ms 2804 KB Output is correct
4 Correct 41 ms 3832 KB Output is correct
5 Correct 14 ms 2792 KB Output is correct
6 Correct 16 ms 2756 KB Output is correct
7 Correct 14 ms 2776 KB Output is correct
8 Correct 16 ms 2784 KB Output is correct
9 Correct 41 ms 3872 KB Output is correct
10 Correct 15 ms 2736 KB Output is correct
11 Correct 127 ms 3868 KB Output is correct
12 Correct 34 ms 3840 KB Output is correct
13 Correct 41 ms 3884 KB Output is correct
14 Correct 43 ms 3916 KB Output is correct
15 Correct 61 ms 3876 KB Output is correct
16 Correct 17 ms 2852 KB Output is correct
17 Correct 28 ms 3876 KB Output is correct
18 Correct 15 ms 2884 KB Output is correct
19 Correct 19 ms 3068 KB Output is correct
20 Correct 18 ms 3044 KB Output is correct
21 Correct 22 ms 2988 KB Output is correct
22 Correct 74 ms 5440 KB Output is correct
23 Correct 64 ms 4912 KB Output is correct
24 Correct 96 ms 5632 KB Output is correct
25 Correct 84 ms 8908 KB Output is correct
26 Correct 58 ms 6464 KB Output is correct
27 Correct 224 ms 16588 KB Output is correct
28 Correct 214 ms 16564 KB Output is correct
29 Correct 230 ms 17928 KB Output is correct
30 Correct 212 ms 17288 KB Output is correct
31 Correct 261 ms 16772 KB Output is correct
32 Correct 747 ms 61692 KB Output is correct
33 Correct 304 ms 22180 KB Output is correct
34 Correct 388 ms 26068 KB Output is correct
35 Correct 34 ms 3784 KB Output is correct
36 Correct 327 ms 21812 KB Output is correct
37 Correct 1352 ms 67364 KB Output is correct
38 Correct 1378 ms 67468 KB Output is correct
39 Correct 1006 ms 46152 KB Output is correct
40 Correct 394 ms 23736 KB Output is correct
41 Correct 180 ms 14740 KB Output is correct
42 Correct 93 ms 9656 KB Output is correct
43 Correct 1452 ms 57208 KB Output is correct
44 Correct 827 ms 37800 KB Output is correct
45 Correct 759 ms 73784 KB Output is correct
46 Correct 1255 ms 387084 KB Output is correct
47 Correct 284 ms 20188 KB Output is correct
48 Correct 998 ms 203248 KB Output is correct
49 Correct 1069 ms 204696 KB Output is correct
50 Correct 263 ms 19728 KB Output is correct
51 Correct 22 ms 3264 KB Output is correct
52 Correct 20 ms 3236 KB Output is correct
53 Correct 22 ms 3216 KB Output is correct
54 Correct 66 ms 6068 KB Output is correct
55 Correct 72 ms 7224 KB Output is correct
56 Correct 89 ms 7192 KB Output is correct
57 Correct 73 ms 7924 KB Output is correct
58 Correct 73 ms 7936 KB Output is correct
59 Correct 95 ms 8948 KB Output is correct
60 Correct 399 ms 29868 KB Output is correct
61 Correct 409 ms 29816 KB Output is correct
62 Correct 405 ms 29804 KB Output is correct
63 Correct 459 ms 9844 KB Output is correct
64 Correct 448 ms 9792 KB Output is correct
65 Correct 477 ms 9856 KB Output is correct
66 Correct 126 ms 8452 KB Output is correct
67 Correct 374 ms 98644 KB Output is correct
68 Correct 421 ms 98664 KB Output is correct
69 Correct 416 ms 98688 KB Output is correct
70 Correct 401 ms 98616 KB Output is correct
71 Correct 421 ms 98608 KB Output is correct
72 Correct 405 ms 98684 KB Output is correct
73 Correct 404 ms 98648 KB Output is correct
74 Correct 414 ms 98608 KB Output is correct
75 Correct 219 ms 18872 KB Output is correct
76 Correct 238 ms 19568 KB Output is correct
77 Correct 252 ms 21804 KB Output is correct
78 Correct 218 ms 19672 KB Output is correct
79 Correct 303 ms 20228 KB Output is correct
80 Correct 213 ms 19752 KB Output is correct
81 Correct 1304 ms 65244 KB Output is correct
82 Correct 1408 ms 65444 KB Output is correct
83 Correct 1570 ms 85808 KB Output is correct
84 Correct 1343 ms 68436 KB Output is correct
85 Correct 1361 ms 63920 KB Output is correct
86 Correct 1388 ms 64476 KB Output is correct
87 Correct 1100 ms 58412 KB Output is correct
88 Correct 711 ms 22804 KB Output is correct
89 Correct 694 ms 22800 KB Output is correct
90 Correct 699 ms 22944 KB Output is correct
91 Correct 699 ms 22912 KB Output is correct
92 Correct 742 ms 22848 KB Output is correct
93 Correct 1905 ms 388484 KB Output is correct
94 Correct 881 ms 91872 KB Output is correct
95 Correct 1987 ms 387200 KB Output is correct
96 Correct 1943 ms 201608 KB Output is correct
97 Correct 960 ms 55012 KB Output is correct
98 Correct 830 ms 61912 KB Output is correct
99 Correct 2667 ms 388392 KB Output is correct
100 Correct 1711 ms 386752 KB Output is correct
101 Correct 995 ms 63952 KB Output is correct
102 Correct 1959 ms 201496 KB Output is correct
103 Correct 857 ms 59532 KB Output is correct
104 Correct 2074 ms 387096 KB Output is correct
105 Correct 362 ms 17472 KB Output is correct
106 Correct 788 ms 112380 KB Output is correct
107 Correct 786 ms 112544 KB Output is correct
108 Correct 769 ms 108712 KB Output is correct
109 Correct 788 ms 112604 KB Output is correct
110 Correct 792 ms 108660 KB Output is correct
111 Correct 848 ms 112604 KB Output is correct
112 Correct 841 ms 112740 KB Output is correct
113 Correct 834 ms 108836 KB Output is correct
114 Correct 838 ms 108680 KB Output is correct
115 Correct 821 ms 108764 KB Output is correct
116 Correct 1053 ms 201020 KB Output is correct