oj.uz

답안 #172315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172315 2020-01-01T07:06:48 Z eggag32 원 고르기 (APIO18_circle_selection) C++17
7 / 100
 737 ms 41080 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.se.fi < b.se.fi);
}

bool cmp2(pair<pair<ld, int>, pair<ld, ld>> a, pair<pair<ld, int>, pair<ld, ld>> b){
	return (a.se.se < b.se.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 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), cmp2); //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 380 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 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 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 10 ms 732 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 131 ms 748 KB Output is correct
23 Correct 134 ms 760 KB Output is correct
24 Correct 139 ms 784 KB Output is correct
25 Correct 132 ms 860 KB Output is correct
26 Correct 132 ms 760 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 719 ms 41080 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 261 ms 13948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 737 ms 41080 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 380 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 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 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 10 ms 732 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 131 ms 748 KB Output is correct
23 Correct 134 ms 760 KB Output is correct
24 Correct 139 ms 784 KB Output is correct
25 Correct 132 ms 860 KB Output is correct
26 Correct 132 ms 760 KB Output is correct
27 Incorrect 26 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 380 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 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 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 10 ms 732 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 131 ms 748 KB Output is correct
23 Correct 134 ms 760 KB Output is correct
24 Correct 139 ms 784 KB Output is correct
25 Correct 132 ms 860 KB Output is correct
26 Correct 132 ms 760 KB Output is correct
27 Incorrect 719 ms 41080 KB Output isn't correct
28 Halted 0 ms 0 KB -