oj.uz

Submission #544151

# Submission time Handle Problem Language Result Execution time Memory
544151 2022-04-01T08:37:54 Z amunduzbaev Circle selection (APIO18_circle_selection) C++17
23 / 100
 476 ms 43560 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);
	vector<int> tot;
	for(int i=0;i<n;i++){
		cin>>a[i].x>>a[i].y>>a[i].r;
	}
	int R = a[0].r;
	auto get = [&](int x){ return (x / R) - (x < 0); };
	for(int i=0;i<n;i++) tot.push_back(get(a[i].x));
	sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	vector<set<ar<int, 2>>> pp(tot.size());
	
	for(int i=0;i<n;i++){
		auto j = lower_bound(tot.begin(), tot.end(), get(a[i].x)) - tot.begin();
		assert(j < (int)tot.size());
		pp[j].insert({a[i].y, i});
	}
	
	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){
		return (2. * R - dis(i, j) > eps);
	};
	
	vector<int> used(n);
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		int l = lower_bound(tot.begin(), tot.end(), get(a[i].x) - 2) - tot.begin();
		int r = upper_bound(tot.begin(), tot.end(), get(a[i].x) + 2) - tot.begin();
		int lx = (get(a[i].y) - 2) * R;
		int rx = (get(a[i].y) + 3) * R;
		for(int j=l;j<r;j++){
			auto it = pp[j].lower_bound({lx, -1});
			vector<ar<int, 2>> er;
			while(it != pp[j].end() && (*it)[0] < rx){
				if(check((*it)[1], i)){
					er.push_back(*it);
				} it++;
			}
			
			for(auto x : er) pp[j].erase(x), used[x[1]] = i + 1;
		}
		assert(used[i] == i + 1);
	}
	
	for(int i=0;i<n;i++) cout<<used[i]<<" ";
	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 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 25988 KB Output is correct
2 Correct 356 ms 37756 KB Output is correct
3 Correct 397 ms 23176 KB Output is correct
4 Correct 385 ms 42660 KB Output is correct
5 Correct 356 ms 43560 KB Output is correct
6 Correct 341 ms 30184 KB Output is correct

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 Incorrect 1 ms 212 KB Output isn't correct
5 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 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -