oj.uz

Submission #258957

# Submission time Handle Problem Language Result Execution time Memory
258957 2020-08-06T21:05:36 Z amoo_safar Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 16492 KB 
// Null
#include <bits/stdc++.h>
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll Mod = 1000000007LL;
const int N = 3e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;


int n, x[N], y[N], r[N];
int mk[N];

map<pii, vector<int>> mp;

void Build(int L){
	mp.clear();
	for(int i = 1; i <= n; i++){
		if(mk[i]) continue;
		mp[{x[i]/L, y[i]/L}].pb(i);
	}
}

int main(){
	ios::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];
	}
	vector<int> I(n); iota(all(I), 1);
	sort(all(I), [&](int i, int j){
		return (r[i] == r[j] ? i < j : r[i] > r[j]);
	});
	int L = 1 << 31;
	Build(L);
	for(auto id : I){
		if(mk[id]) continue;
		int fl = 0;
		while(L >= r[id] + r[id]) L >>= 1, fl = 1;
		if(fl) Build(L);
		int i = x[id] / L;
		int j = y[id] / L;
		for(int i2 = i - 2; i2 <= i + 2; i2 ++) for(int j2 = j - 2; j2 <= j + 2; j2 ++){
			if(mp.count({i2, j2})){
				for(auto &nei : mp[{i2, j2}]){
					if(mk[nei]) continue;
					if(1ll*(x[id] - x[nei])*(x[id] - x[nei]) + 1ll*(y[id] - y[nei])*(y[id] - y[nei]) <= 1ll*(r[id] + r[nei])*(r[id] + r[nei]) ){
						mk[nei] = id;
					}
				}
			}
		}
	}
	
	for(int i = 1; i <= n; i++) cout << mk[i] << ' ';
	cout << '\n';
	return 0;
}
/*
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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 512 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 92 ms 568 KB Output is correct
23 Correct 92 ms 512 KB Output is correct
24 Correct 107 ms 512 KB Output is correct
25 Correct 105 ms 512 KB Output is correct
26 Correct 98 ms 632 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 16052 KB Output is correct
2 Correct 176 ms 16492 KB Output is correct
3 Correct 210 ms 16056 KB Output is correct
4 Correct 171 ms 16364 KB Output is correct
5 Execution timed out 3078 ms 12140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Execution timed out 3072 ms 5296 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 3067 ms 14704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 512 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 92 ms 568 KB Output is correct
23 Correct 92 ms 512 KB Output is correct
24 Correct 107 ms 512 KB Output is correct
25 Correct 105 ms 512 KB Output is correct
26 Correct 98 ms 632 KB Output is correct
27 Correct 6 ms 768 KB Output is correct
28 Correct 7 ms 1024 KB Output is correct
29 Correct 6 ms 1024 KB Output is correct
30 Correct 395 ms 1016 KB Output is correct
31 Correct 415 ms 1016 KB Output is correct
32 Correct 407 ms 1016 KB Output is correct
33 Correct 65 ms 6644 KB Output is correct
34 Correct 67 ms 6516 KB Output is correct
35 Correct 69 ms 6388 KB Output is correct
36 Execution timed out 3057 ms 5312 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 512 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 92 ms 568 KB Output is correct
23 Correct 92 ms 512 KB Output is correct
24 Correct 107 ms 512 KB Output is correct
25 Correct 105 ms 512 KB Output is correct
26 Correct 98 ms 632 KB Output is correct
27 Correct 178 ms 16052 KB Output is correct
28 Correct 176 ms 16492 KB Output is correct
29 Correct 210 ms 16056 KB Output is correct
30 Correct 171 ms 16364 KB Output is correct
31 Execution timed out 3078 ms 12140 KB Time limit exceeded
32 Halted 0 ms 0 KB -