oj.uz

Submission #49666

# Submission time Handle Problem Language Result Execution time Memory
49666 2018-06-01T18:55:26 Z gs14004 Circle selection (APIO18_circle_selection) C++17
15 / 100
 1786 ms 24288 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
const int offs = 1e9 + 100;
using pi = pair<int, int>;

struct circ{
	int x, y, r, idx;
	bool operator<(const circ &c)const{
		return pi(x, y) < pi(c.x, c.y);
	}
}a[MAXN], orig_pos[MAXN];

int n, ans[MAXN];

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].r);
		a[i].idx = i + 1;
		orig_pos[i + 1] = a[i];
	}
	auto inter = [&](circ a, circ b){
		int dx = a.x - b.x;
		int dy = a.y - b.y;
		int dr = a.r + b.r;
		return 1ll * dx * dx + 1ll * dy * dy <= 1ll * dr * dr;
	};
	sort(a, a+n, [&](const circ &a, const circ &b){
		return pi(-a.r, a.idx) < pi(-b.r, b.idx);
	});
	for(int i=30; i; i--){
		int lb = (1 << (i - 1)), rb = (1 << i) - 1;
		vector<circ> v;
		for(int j=0; j<n; j++){
			if(!ans[a[j].idx] && a[j].r <= rb){
				v.push_back((circ){(a[j].x + offs) >> i, (a[j].y + offs) >> i, a[j].r, a[j].idx});
			}
		}
		sort(v.begin(), v.end());
		for(int j=0; j<n; j++){
			if(!ans[a[j].idx] && a[j].r <= rb && a[j].r >= lb){
				for(int k=-2; k<=2; k++){
					int px = ((a[j].x + offs) >> i) + k;
					int py = ((a[j].y + offs) >> i) - 2;
					auto itr = lower_bound(v.begin(), v.end(), (circ){px, py, -1, -1}) - v.begin();
					while(itr < v.size() && pi(v[itr].x, v[itr].y) <= pi(px, py + 4)){
						if(inter(orig_pos[v[itr].idx], a[j])){
							ans[v[itr].idx] = a[j].idx;
						}
						itr++;
					}
				}
			}
		}
	}
	for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while(itr < v.size() && pi(v[itr].x, v[itr].y) <= pi(px, py + 4)){
            ~~~~^~~~~~~~~~
circle_selection.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Incorrect 3 ms 716 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 24004 KB Output is correct
2 Incorrect 419 ms 24184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24184 KB Output is correct
2 Correct 374 ms 24184 KB Output is correct
3 Correct 1387 ms 24184 KB Output is correct
4 Correct 1287 ms 24224 KB Output is correct
5 Correct 1012 ms 24224 KB Output is correct
6 Correct 482 ms 24224 KB Output is correct
7 Correct 240 ms 24224 KB Output is correct
8 Correct 49 ms 24224 KB Output is correct
9 Correct 1165 ms 24224 KB Output is correct
10 Correct 948 ms 24224 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 24224 KB Output is correct
2 Correct 1786 ms 24288 KB Output is correct
3 Incorrect 626 ms 24288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Incorrect 3 ms 716 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Incorrect 3 ms 716 KB Output isn't correct
11 Halted 0 ms 0 KB -