oj.uz

Submission #732740

# Submission time Handle Problem Language Result Execution time Memory
732740 2023-04-29T08:48:59 Z minhcool Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 126672 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, x[N], y[N], r[N];
 
int ans[N];
 
bool out[N];
 
unordered_map<int, int> mp;
vector<ii> vc[N];
 
bool ck(int i, int j){
//	cout << i << " " << j << "\n";
	int dist = ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
	int rd = (r[i] + r[j]) * (r[i] + r[j]);
	return (dist <= rd);
}
 
void process(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
	set<ii> rem;
	for(int i = 1; i <= n; i++) rem.insert({-r[i], i});
	bool chk = 1;
	for(int i = 1; i <= n; i++) chk &= (r[i] == 1);
	if(chk){
		for(int i = 1; i <= n; i++) cout << i << " ";
		cout << "\n";
		exit(0);
	}
	for(int i = 32; i >= 0; i--){// executing with radius (1LL << (i - 1)) to (1LL << i)
		int rad = (1LL << i);
		mp.clear();
		for(int j = 1; j <= n; j++) vc[j].clear();
		vector<int> diff;
		for(int j = 1; j <= n; j++) if(!out[j]) diff.pb(x[j] / rad);
		sort(diff.begin(), diff.end());
		diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
		for(int j = 0; j < diff.size(); j++) mp[diff[j]] = j + 1;
		for(int j = 1; j <= n; j++){
			if(!out[j]){
				//cout << "OK " << rad << " " << j << " " << x[j]/rad << " " << y[j] << "\n";
				vc[mp[x[j]/rad]].pb({y[j], j});
			}
		}
		for(int j = 1; j <= n; j++) sort(vc[j].begin(), vc[j].end());
		while(!rem.empty() && -((*rem.begin()).fi) >= (1LL << (i - 1))){
			int ind = (*rem.begin()).se;
		//	cout << rad << " " << ind << "\n";
			assert(!out[ind]);
			out[ind] = 1;
			ans[ind] = ind;
			rem.erase({-r[ind], ind});
			for(int i2 = x[ind]/rad - 4; i2 <= x[ind]/rad + 5; i2++){
				if(mp.find(i2) == mp.end()) continue;
				int temp = mp[i2];
				int le = (y[ind]/rad) - 4, ri = (y[ind] / rad) + 5;
			//	cout << 
				le *= rad, ri *= rad;
			//	cout << le << " " << ri << "\n";
				vector<ii>::iterator it = lower_bound(vc[temp].begin(), vc[temp].end(), make_pair(le, -oo));
				for(; it != vc[temp].end(); it++){
					if((*it).fi > ri) break;
					if(out[(*it).se]) continue;
					if(ck(ind, (*it).se)){
						//cout << ind << " " << (*it).se << "\n";
						ans[(*it).se] = ind;
						rem.erase({-r[(*it).se], (*it).se});
						out[(*it).se] = 1;
					}
				}
			}
		}
	}
	for(int i = 1; i <= n; i++) if(!ans[i]) ans[i] = i;
	for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

Compilation message

circle_selection.cpp: In function 'void process()':
circle_selection.cpp:54:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int j = 0; j < diff.size(); j++) mp[diff[j]] = j + 1;
      |                  ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7392 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7316 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 6 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 5 ms 7480 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 9 ms 8168 KB Output is correct
20 Correct 10 ms 8084 KB Output is correct
21 Correct 9 ms 8148 KB Output is correct
22 Correct 22 ms 8788 KB Output is correct
23 Correct 21 ms 8532 KB Output is correct
24 Correct 22 ms 8932 KB Output is correct
25 Correct 23 ms 8920 KB Output is correct
26 Correct 22 ms 8916 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 46900 KB Output is correct
2 Correct 596 ms 54140 KB Output is correct
3 Correct 567 ms 54652 KB Output is correct
4 Correct 471 ms 46912 KB Output is correct
5 Correct 1194 ms 80880 KB Output is correct
6 Correct 1533 ms 113592 KB Output is correct
7 Correct 1244 ms 87240 KB Output is correct
8 Correct 1307 ms 103688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 396 ms 32588 KB Output is correct
3 Correct 1556 ms 98108 KB Output is correct
4 Correct 1549 ms 98428 KB Output is correct
5 Correct 1391 ms 86728 KB Output is correct
6 Correct 626 ms 50440 KB Output is correct
7 Correct 309 ms 30244 KB Output is correct
8 Correct 62 ms 12400 KB Output is correct
9 Correct 1558 ms 99444 KB Output is correct
10 Correct 1323 ms 81292 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 97552 KB Output is correct
2 Correct 152 ms 35148 KB Output is correct
3 Correct 1018 ms 66224 KB Output is correct
4 Correct 1956 ms 111380 KB Output is correct
5 Correct 2177 ms 124612 KB Output is correct
6 Correct 985 ms 66996 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7392 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7316 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 6 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 5 ms 7480 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 9 ms 8168 KB Output is correct
20 Correct 10 ms 8084 KB Output is correct
21 Correct 9 ms 8148 KB Output is correct
22 Correct 22 ms 8788 KB Output is correct
23 Correct 21 ms 8532 KB Output is correct
24 Correct 22 ms 8932 KB Output is correct
25 Correct 23 ms 8920 KB Output is correct
26 Correct 22 ms 8916 KB Output is correct
27 Correct 16 ms 8672 KB Output is correct
28 Correct 17 ms 8660 KB Output is correct
29 Correct 16 ms 8672 KB Output is correct
30 Correct 39 ms 9768 KB Output is correct
31 Correct 41 ms 10496 KB Output is correct
32 Correct 39 ms 10344 KB Output is correct
33 Correct 157 ms 20244 KB Output is correct
34 Correct 154 ms 20152 KB Output is correct
35 Correct 175 ms 22924 KB Output is correct
36 Correct 452 ms 38888 KB Output is correct
37 Correct 466 ms 37572 KB Output is correct
38 Correct 466 ms 35460 KB Output is correct
39 Correct 622 ms 29888 KB Output is correct
40 Correct 644 ms 29972 KB Output is correct
41 Correct 638 ms 29896 KB Output is correct
42 Correct 470 ms 27688 KB Output is correct
43 Correct 589 ms 45904 KB Output is correct
44 Correct 571 ms 45852 KB Output is correct
45 Correct 549 ms 45748 KB Output is correct
46 Correct 620 ms 45780 KB Output is correct
47 Correct 560 ms 45832 KB Output is correct
48 Correct 563 ms 45860 KB Output is correct
49 Correct 541 ms 45648 KB Output is correct
50 Correct 553 ms 45816 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7392 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7316 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 5 ms 7380 KB Output is correct
12 Correct 6 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 5 ms 7480 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 9 ms 8168 KB Output is correct
20 Correct 10 ms 8084 KB Output is correct
21 Correct 9 ms 8148 KB Output is correct
22 Correct 22 ms 8788 KB Output is correct
23 Correct 21 ms 8532 KB Output is correct
24 Correct 22 ms 8932 KB Output is correct
25 Correct 23 ms 8920 KB Output is correct
26 Correct 22 ms 8916 KB Output is correct
27 Correct 521 ms 46900 KB Output is correct
28 Correct 596 ms 54140 KB Output is correct
29 Correct 567 ms 54652 KB Output is correct
30 Correct 471 ms 46912 KB Output is correct
31 Correct 1194 ms 80880 KB Output is correct
32 Correct 1533 ms 113592 KB Output is correct
33 Correct 1244 ms 87240 KB Output is correct
34 Correct 1307 ms 103688 KB Output is correct
35 Correct 3 ms 7380 KB Output is correct
36 Correct 396 ms 32588 KB Output is correct
37 Correct 1556 ms 98108 KB Output is correct
38 Correct 1549 ms 98428 KB Output is correct
39 Correct 1391 ms 86728 KB Output is correct
40 Correct 626 ms 50440 KB Output is correct
41 Correct 309 ms 30244 KB Output is correct
42 Correct 62 ms 12400 KB Output is correct
43 Correct 1558 ms 99444 KB Output is correct
44 Correct 1323 ms 81292 KB Output is correct
45 Correct 1436 ms 97552 KB Output is correct
46 Correct 152 ms 35148 KB Output is correct
47 Correct 1018 ms 66224 KB Output is correct
48 Correct 1956 ms 111380 KB Output is correct
49 Correct 2177 ms 124612 KB Output is correct
50 Correct 985 ms 66996 KB Output is correct
51 Correct 16 ms 8672 KB Output is correct
52 Correct 17 ms 8660 KB Output is correct
53 Correct 16 ms 8672 KB Output is correct
54 Correct 39 ms 9768 KB Output is correct
55 Correct 41 ms 10496 KB Output is correct
56 Correct 39 ms 10344 KB Output is correct
57 Correct 157 ms 20244 KB Output is correct
58 Correct 154 ms 20152 KB Output is correct
59 Correct 175 ms 22924 KB Output is correct
60 Correct 452 ms 38888 KB Output is correct
61 Correct 466 ms 37572 KB Output is correct
62 Correct 466 ms 35460 KB Output is correct
63 Correct 622 ms 29888 KB Output is correct
64 Correct 644 ms 29972 KB Output is correct
65 Correct 638 ms 29896 KB Output is correct
66 Correct 470 ms 27688 KB Output is correct
67 Correct 589 ms 45904 KB Output is correct
68 Correct 571 ms 45852 KB Output is correct
69 Correct 549 ms 45748 KB Output is correct
70 Correct 620 ms 45780 KB Output is correct
71 Correct 560 ms 45832 KB Output is correct
72 Correct 563 ms 45860 KB Output is correct
73 Correct 541 ms 45648 KB Output is correct
74 Correct 553 ms 45816 KB Output is correct
75 Correct 711 ms 51024 KB Output is correct
76 Correct 774 ms 53420 KB Output is correct
77 Correct 717 ms 46948 KB Output is correct
78 Correct 641 ms 46900 KB Output is correct
79 Correct 872 ms 53208 KB Output is correct
80 Correct 650 ms 46900 KB Output is correct
81 Correct 1696 ms 100976 KB Output is correct
82 Correct 1640 ms 93720 KB Output is correct
83 Correct 1731 ms 106676 KB Output is correct
84 Correct 1607 ms 98872 KB Output is correct
85 Correct 1663 ms 98688 KB Output is correct
86 Correct 1688 ms 97184 KB Output is correct
87 Correct 1581 ms 76504 KB Output is correct
88 Correct 2432 ms 81424 KB Output is correct
89 Correct 2538 ms 81300 KB Output is correct
90 Correct 2773 ms 81340 KB Output is correct
91 Correct 2618 ms 80864 KB Output is correct
92 Correct 2829 ms 81016 KB Output is correct
93 Correct 2942 ms 125180 KB Output is correct
94 Correct 1768 ms 46956 KB Output is correct
95 Execution timed out 3056 ms 126672 KB Time limit exceeded
96 Halted 0 ms 0 KB -