oj.uz

Submission #700149

# Submission time Handle Problem Language Result Execution time Memory
700149 2023-02-18T17:50:12 Z ymm Circle selection (APIO18_circle_selection) C++17
100 / 100
 2891 ms 55820 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 300'010;
ll r[N], x[N], y[N];
 
inline ll sqr(ll x){return x*x;}
inline bool g(int i, int j){return sqr(x[i]-x[j]) + sqr(y[i]-y[j]) <= sqr(r[i]+r[j]);}

template<>
struct std::hash<pii>
{
	size_t operator()(const pii &x) const {
		return hash<ll>()(*(ll *)&x);
	}
};
 
unordered_map<pii, vector<pii>> mp[32];
int ans[N];
pll circ[N];
int n;
 
int main()
{
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n;
    Loop(i,0,n)
    {
        cin >> x[i] >> y[i] >> r[i];
        x[i] += 1e9; y[i] += 1e9;
        circ[i] = {~r[i], i};
    }
    sort(circ, circ+n);
    Loop(_,0,n)
    {
        int i = circ[_].second;
        int lg = r[i]==1?0:32-__builtin_clz(r[i]-1);
        int mn = 1e9;
        for(int k = lg; k < 32; ++k)
        {
            ll r = k? 1<<(k-1): 0;
            ll d = r? 2*r: 1;
            // (r, d]
            Loop(xx,-1,2) Loop(yy,-1,2){
                auto tmp = mp[k].find(pii{x[i]/(2*d)+xx, y[i]/(2*d)+yy});
                if(tmp == mp[k].end()) continue;
                for(auto [j1, j2] : tmp->second){
                    if(g(i,j2)){
                        mn = min(j1, mn);
                        break;
                    }
                }
            }
        }
        if(mn == 1e9){
            ll r = lg? 1<<(lg-1): 0;
            ll d = r? 2*r: 1;
            mp[lg][pll{x[i]/(2*d), y[i]/(2*d)}].emplace_back(_, i);
            ans[i] = i;
        } else ans[i] = circ[mn].second;
    }
    Loop(i,0,n) cout << ans[i]+1 << ' ';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 396 KB Output is correct
19 Correct 6 ms 724 KB Output is correct
20 Correct 5 ms 724 KB Output is correct
21 Correct 6 ms 724 KB Output is correct
22 Correct 24 ms 1228 KB Output is correct
23 Correct 26 ms 1156 KB Output is correct
24 Correct 23 ms 1176 KB Output is correct
25 Correct 26 ms 1228 KB Output is correct
26 Correct 24 ms 1196 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 22004 KB Output is correct
2 Correct 399 ms 21960 KB Output is correct
3 Correct 410 ms 21656 KB Output is correct
4 Correct 299 ms 22008 KB Output is correct
5 Correct 1773 ms 20300 KB Output is correct
6 Correct 2209 ms 29508 KB Output is correct
7 Correct 1828 ms 21024 KB Output is correct
8 Correct 1895 ms 22612 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 525 ms 18192 KB Output is correct
3 Correct 1966 ms 55576 KB Output is correct
4 Correct 1956 ms 55568 KB Output is correct
5 Correct 1842 ms 45516 KB Output is correct
6 Correct 770 ms 20480 KB Output is correct
7 Correct 381 ms 10896 KB Output is correct
8 Correct 69 ms 2452 KB Output is correct
9 Correct 2244 ms 53540 KB Output is correct
10 Correct 1763 ms 39092 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 54032 KB Output is correct
2 Correct 2403 ms 53304 KB Output is correct
3 Correct 876 ms 24500 KB Output is correct
4 Correct 1838 ms 53640 KB Output is correct
5 Correct 1873 ms 53856 KB Output is correct
6 Correct 742 ms 23160 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 396 KB Output is correct
19 Correct 6 ms 724 KB Output is correct
20 Correct 5 ms 724 KB Output is correct
21 Correct 6 ms 724 KB Output is correct
22 Correct 24 ms 1228 KB Output is correct
23 Correct 26 ms 1156 KB Output is correct
24 Correct 23 ms 1176 KB Output is correct
25 Correct 26 ms 1228 KB Output is correct
26 Correct 24 ms 1196 KB Output is correct
27 Correct 13 ms 1092 KB Output is correct
28 Correct 14 ms 1108 KB Output is correct
29 Correct 13 ms 1048 KB Output is correct
30 Correct 47 ms 2124 KB Output is correct
31 Correct 50 ms 2048 KB Output is correct
32 Correct 50 ms 2092 KB Output is correct
33 Correct 113 ms 8276 KB Output is correct
34 Correct 104 ms 8240 KB Output is correct
35 Correct 144 ms 8136 KB Output is correct
36 Correct 601 ms 18552 KB Output is correct
37 Correct 599 ms 18308 KB Output is correct
38 Correct 590 ms 18772 KB Output is correct
39 Correct 791 ms 9568 KB Output is correct
40 Correct 780 ms 9700 KB Output is correct
41 Correct 784 ms 9620 KB Output is correct
42 Correct 530 ms 8240 KB Output is correct
43 Correct 528 ms 17708 KB Output is correct
44 Correct 583 ms 17724 KB Output is correct
45 Correct 528 ms 17596 KB Output is correct
46 Correct 519 ms 17632 KB Output is correct
47 Correct 537 ms 17704 KB Output is correct
48 Correct 565 ms 17668 KB Output is correct
49 Correct 543 ms 17636 KB Output is correct
50 Correct 534 ms 17744 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 396 KB Output is correct
19 Correct 6 ms 724 KB Output is correct
20 Correct 5 ms 724 KB Output is correct
21 Correct 6 ms 724 KB Output is correct
22 Correct 24 ms 1228 KB Output is correct
23 Correct 26 ms 1156 KB Output is correct
24 Correct 23 ms 1176 KB Output is correct
25 Correct 26 ms 1228 KB Output is correct
26 Correct 24 ms 1196 KB Output is correct
27 Correct 352 ms 22004 KB Output is correct
28 Correct 399 ms 21960 KB Output is correct
29 Correct 410 ms 21656 KB Output is correct
30 Correct 299 ms 22008 KB Output is correct
31 Correct 1773 ms 20300 KB Output is correct
32 Correct 2209 ms 29508 KB Output is correct
33 Correct 1828 ms 21024 KB Output is correct
34 Correct 1895 ms 22612 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 525 ms 18192 KB Output is correct
37 Correct 1966 ms 55576 KB Output is correct
38 Correct 1956 ms 55568 KB Output is correct
39 Correct 1842 ms 45516 KB Output is correct
40 Correct 770 ms 20480 KB Output is correct
41 Correct 381 ms 10896 KB Output is correct
42 Correct 69 ms 2452 KB Output is correct
43 Correct 2244 ms 53540 KB Output is correct
44 Correct 1763 ms 39092 KB Output is correct
45 Correct 1613 ms 54032 KB Output is correct
46 Correct 2403 ms 53304 KB Output is correct
47 Correct 876 ms 24500 KB Output is correct
48 Correct 1838 ms 53640 KB Output is correct
49 Correct 1873 ms 53856 KB Output is correct
50 Correct 742 ms 23160 KB Output is correct
51 Correct 13 ms 1092 KB Output is correct
52 Correct 14 ms 1108 KB Output is correct
53 Correct 13 ms 1048 KB Output is correct
54 Correct 47 ms 2124 KB Output is correct
55 Correct 50 ms 2048 KB Output is correct
56 Correct 50 ms 2092 KB Output is correct
57 Correct 113 ms 8276 KB Output is correct
58 Correct 104 ms 8240 KB Output is correct
59 Correct 144 ms 8136 KB Output is correct
60 Correct 601 ms 18552 KB Output is correct
61 Correct 599 ms 18308 KB Output is correct
62 Correct 590 ms 18772 KB Output is correct
63 Correct 791 ms 9568 KB Output is correct
64 Correct 780 ms 9700 KB Output is correct
65 Correct 784 ms 9620 KB Output is correct
66 Correct 530 ms 8240 KB Output is correct
67 Correct 528 ms 17708 KB Output is correct
68 Correct 583 ms 17724 KB Output is correct
69 Correct 528 ms 17596 KB Output is correct
70 Correct 519 ms 17632 KB Output is correct
71 Correct 537 ms 17704 KB Output is correct
72 Correct 565 ms 17668 KB Output is correct
73 Correct 543 ms 17636 KB Output is correct
74 Correct 534 ms 17744 KB Output is correct
75 Correct 381 ms 24376 KB Output is correct
76 Correct 476 ms 24056 KB Output is correct
77 Correct 421 ms 24216 KB Output is correct
78 Correct 314 ms 24020 KB Output is correct
79 Correct 601 ms 23924 KB Output is correct
80 Correct 319 ms 23980 KB Output is correct
81 Correct 2308 ms 54232 KB Output is correct
82 Correct 2078 ms 54028 KB Output is correct
83 Correct 2076 ms 55360 KB Output is correct
84 Correct 2009 ms 55820 KB Output is correct
85 Correct 2029 ms 55244 KB Output is correct
86 Correct 2079 ms 54376 KB Output is correct
87 Correct 2045 ms 54964 KB Output is correct
88 Correct 2521 ms 28744 KB Output is correct
89 Correct 2530 ms 28752 KB Output is correct
90 Correct 2470 ms 28840 KB Output is correct
91 Correct 2469 ms 28868 KB Output is correct
92 Correct 2486 ms 28880 KB Output is correct
93 Correct 2856 ms 53612 KB Output is correct
94 Correct 2615 ms 52960 KB Output is correct
95 Correct 2891 ms 53672 KB Output is correct
96 Correct 2631 ms 52884 KB Output is correct
97 Correct 2657 ms 54236 KB Output is correct
98 Correct 2295 ms 33832 KB Output is correct
99 Correct 2569 ms 54400 KB Output is correct
100 Correct 2689 ms 53112 KB Output is correct
101 Correct 2437 ms 38120 KB Output is correct
102 Correct 2538 ms 52184 KB Output is correct
103 Correct 2652 ms 51900 KB Output is correct
104 Correct 2615 ms 53188 KB Output is correct
105 Correct 1724 ms 24240 KB Output is correct
106 Correct 1721 ms 47104 KB Output is correct
107 Correct 1712 ms 47256 KB Output is correct
108 Correct 1738 ms 47204 KB Output is correct
109 Correct 1729 ms 47152 KB Output is correct
110 Correct 1741 ms 47208 KB Output is correct
111 Correct 1723 ms 47220 KB Output is correct
112 Correct 1904 ms 47112 KB Output is correct
113 Correct 1712 ms 47112 KB Output is correct
114 Correct 1755 ms 47152 KB Output is correct
115 Correct 1757 ms 47284 KB Output is correct
116 Correct 1729 ms 47108 KB Output is correct