oj.uz

답안 #172310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172310 2020-01-01T06:45:10 Z eggag32 원 고르기 (APIO18_circle_selection) C++17
7 / 100
 644 ms 42348 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

bool cmp(pair<pair<ld, int>, pair<ld, ld>> a, pair<pair<ld, int>, pair<ld, ld>> b){
	if(a.fi.fi != b.fi.fi) return (a.fi.fi > b.fi.fi);
	return (a.fi.se < b.fi.se);
}

bool cmp1(pair<pair<ld, int>, pair<ld, ld>> a, pair<pair<ld, int>, pair<ld, ld>> b){
	return (a.fi.fi < b.fi.fi);
}

bool cmp2(pair<pair<ld, int>, pair<ld, ld>> a, pair<pair<ld, int>, pair<ld, ld>> b){
	return (a.fi.se < b.fi.se);
}

ld dist(ld x, ld y, ld x1, ld y1){
	return sqrtl(sq(x1 - x) + sq(y1 - y));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	vector<pair<pair<ld, int>, pair<ld, ld>>> c(n);
	int yis0 = 1;
	rep(i, n){
		cin >> c[i].se.fi >> c[i].se.se >> c[i].fi.fi;
		if(c[i].se.se != 0) yis0 = 0;
		c[i].fi.se = i;
	}
	sort(all(c), cmp);
	if(n <= 5000){
		vi vis(n, 0);
		vi ans(n, 0);
		//they are sorted in the way they appear
		rep(i, n) if(!vis[i]){
			repn(j, i + 1, n) if(!vis[j]){
				if(dist(c[i].se.fi, c[i].se.se, c[j].se.fi, c[j].se.se) <= (c[i].fi.fi + c[j].fi.fi)){
					//they intersect
					vis[j] = 1;
					ans[c[j].fi.se] = c[i].fi.se;
				}
			}
			vis[i] = 1;
			ans[c[i].fi.se] = c[i].fi.se;
		}
		rep(i, n) cout << ans[i] + 1 << " ";
		cout << endl;
		return 0;
	}
	/*
	else if(yis0){
		//well, I only got as far as so as putting all endpoints in a vector, so
		//not that far, but I got something
	}
	*/
	else{
		//sort them by y and by x, for each circle, when you find
		//some other circle it intersects, they are both deleted by the
		//one with the larger r[i], or minimum i in case of a tie
		vector<pair<pair<ld, int>, pair<ld, ld>>> c1 = c;
		sort(all(c1), cmp1); //sort by x
		vi vis(n, 0);
		vi ans(n, -1);
		rep(i, c1.size() - 1){
				if(dist(c1[i].se.fi, c1[i].se.se, c1[i + 1].se.fi, c1[i + 1].se.se) <= (c1[i].fi.fi + c1[i + 1].fi.fi)){
					int best = i;
					if(c1[i].fi.fi < c1[i + 1].fi.fi) best = i + 1;
					else if(c1[i].fi.fi == c1[i + 1].fi.fi){
						if(c1[i].fi.se > c1[i + 1].fi.se) best = i + 1;
					}
					if(best == i) best = c1[i].fi.se;
					else best = c1[i + 1].fi.se;
					ans[c1[i].fi.se] = best;
					ans[c1[i + 1].fi.se] = best;
				}
		}
		c1 = c;
		sort(all(c1), cmp1); //sort by y
		rep(i, c1.size() - 1){
				if(dist(c1[i].se.fi, c1[i].se.se, c1[i + 1].se.fi, c1[i + 1].se.se) <= (c1[i].fi.fi + c1[i + 1].fi.fi)){
					int best = i;
					if(c1[i].fi.fi < c1[i + 1].fi.fi) best = i + 1;
					else if(c1[i].fi.fi == c1[i + 1].fi.fi){
						if(c1[i].fi.se > c1[i + 1].fi.se) best = i + 1;
					}
					if(best == i) best = c1[i].fi.se;
					else best = c1[i + 1].fi.se;
					ans[c1[i].fi.se] = best;
					ans[c1[i + 1].fi.se] = best;
				}
		}
		rep(i, ans.size()){
			if(ans[i] == -1) ans[i] = i;
			cout << ans[i] + 1 << " ";
		}
		cout << endl;
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:49:6: warning: variable 'yis0' set but not used [-Wunused-but-set-variable]
  int yis0 = 1;
      ^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Correct 11 ms 760 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 126 ms 860 KB Output is correct
23 Correct 122 ms 760 KB Output is correct
24 Correct 122 ms 752 KB Output is correct
25 Correct 120 ms 860 KB Output is correct
26 Correct 120 ms 760 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 642 ms 42320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 235 ms 14220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 644 ms 42348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Correct 11 ms 760 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 126 ms 860 KB Output is correct
23 Correct 122 ms 760 KB Output is correct
24 Correct 122 ms 752 KB Output is correct
25 Correct 120 ms 860 KB Output is correct
26 Correct 120 ms 760 KB Output is correct
27 Incorrect 24 ms 1656 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 10 ms 760 KB Output is correct
20 Correct 11 ms 760 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 126 ms 860 KB Output is correct
23 Correct 122 ms 760 KB Output is correct
24 Correct 122 ms 752 KB Output is correct
25 Correct 120 ms 860 KB Output is correct
26 Correct 120 ms 760 KB Output is correct
27 Incorrect 642 ms 42320 KB Output isn't correct
28 Halted 0 ms 0 KB -