oj.uz

Submission #111872

# Submission time Handle Problem Language Result Execution time Memory
111872 2019-05-16T13:12:08 Z square1001 Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 15464 KB 
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class point2d {
	public:
	long long x, y;
	point2d() : x(0), y(0) {};
	point2d(long long x_, long long y_) : x(x_), y(y_) {};
	point2d& operator+=(const point2d& p) { x += p.x; y += p.y; return *this; }
	point2d& operator-=(const point2d& p) { x -= p.x; y -= p.y; return *this; }
	point2d operator+(const point2d& p) const { return point2d(*this) += p; }
	point2d operator-(const point2d& p) const { return point2d(*this) -= p; }
	long long norm() const { return x * x + y * y; }
};
int main() {
	int n;
	cin >> n;
	vector<point2d> p(n);
	vector<long long> r(n);
	for(int i = 0; i < n; ++i) {
		cin >> p[i].x >> p[i].y >> r[i];
	}
	vector<int> ans(n, -1);
	while(true) {
		int ptr = -1; long long radius = -1;
		for(int i = 0; i < n; ++i) {
			if(ans[i] != -1) continue;
			if(radius < r[i]) {
				radius = r[i];
				ptr = i;
			}
		}
		if(ptr == -1) break;
		for(int i = 0; i < n; ++i) {
			if((p[ptr] - p[i]).norm() <= 1LL * (r[ptr] + r[i]) * (r[ptr] + r[i])) {
				ans[i] = ptr;
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		if(i) cout << ' ';
		cout << ans[i] + 1;
	}
	cout << endl;
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Incorrect 3 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Execution timed out 3036 ms 5880 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 3016 ms 13468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Incorrect 3 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Incorrect 3 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -