oj.uz

Submission #544131

# Submission time Handle Problem Language Result Execution time Memory
544131 2022-04-01T06:07:48 Z amunduzbaev Circle selection (APIO18_circle_selection) C++17
15 / 100
 545 ms 19028 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
const double eps = 1e-9;

struct poi{
	int x, y, r;
};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<poi> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i].x>>a[i].y>>a[i].r;
	}
	
	vector<int> in(n); iota(in.begin(), in.end(), 0);
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	sort(in.begin(), in.end(), [&](int i, int j){
		return (a[i].x - a[i].r < a[j].x - a[j].r);
	});
	
	sort(out.begin(), out.end(), [&](int i, int j){
		return (a[i].x + a[i].r < a[j].x + a[j].r);
	});
	
	set<ar<int, 2>> ss;
	vector<int> par(n, -1);
	
	auto sq = [&](int x) { return x * 1ll * x; };
	auto dis = [&](int i, int j) -> double{
		return sqrt(sq(a[i].x - a[j].x) + sq(a[i].y - a[j].y));
	};
	
	auto check = [&](int i, int j){
		if(a[i].r + a[j].r - dis(i, j) > eps){
			par[i] = j, par[j] = i;
		}
	};
	
	auto add = [&](int i){
		auto it = ss.lower_bound({a[i].y, i});
		if(it != ss.end()) check((*it)[1], i);
		if(it != ss.begin()) check((*--it)[1], i);
		ss.insert({a[i].y, i});
	};
	
	auto del = [&](int i){
		ss.erase({a[i].y, i});
		auto it = ss.lower_bound({a[i].y, i});
		if(it != ss.end() && it != ss.begin()){
			auto L = it; L--;
			check((*it)[1], (*L)[1]);
		}
	};
	
	int j=0;
	for(auto i : in){
		while(j < n && a[out[j]].x + a[out[j]].r < a[i].x - a[i].r){
			del(out[j++]);
		}
		
		add(i);
	}
	
	for(int i=0;i<n;i++){
		if(par[i] == -1) cout<<i + 1<<" ";
		else {
			if(a[par[i]].r > a[i].r || (a[par[i]].r == a[i].r && par[i] < i)) cout<<par[i] + 1<<" ";
			else cout<<i + 1<<" ";
		}
	}
	
	cout<<"\n";
}

/*

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 545 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 89 ms 5968 KB Output is correct
3 Correct 267 ms 17400 KB Output is correct
4 Correct 266 ms 17484 KB Output is correct
5 Correct 299 ms 17100 KB Output is correct
6 Correct 147 ms 9320 KB Output is correct
7 Correct 72 ms 4980 KB Output is correct
8 Correct 12 ms 1364 KB Output is correct
9 Correct 270 ms 17412 KB Output is correct
10 Correct 313 ms 17792 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 9572 KB Output is correct
2 Correct 197 ms 16376 KB Output is correct
3 Incorrect 349 ms 17908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -