oj.uz

Submission #544147

# Submission time Handle Problem Language Result Execution time Memory
544147 2022-04-01T08:32:23 Z amunduzbaev Circle selection (APIO18_circle_selection) C++17
0 / 100
 445 ms 26864 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;
	for(int i=0;i<n;i++) tot.push_back(a[i].x / R);
	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(), a[i].x / R) - 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 (R + 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(), a[i].x / R - 2) - tot.begin();
		int r = upper_bound(tot.begin(), tot.end(), a[i].x / R + 2) - tot.begin();
		for(int j=l;j<r;j++){
			int lx = (a[i].y / R - 2) * R;
			int rx = (a[i].y / R + 3) * R;
			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 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 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 217 ms 24044 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
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 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 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -