oj.uz

답안 #172313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172313 2020-01-01T06:49:05 Z eggag32 원 고르기 (APIO18_circle_selection) C++17
7 / 100
 691 ms 42388 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), 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 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 376 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 4 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 760 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 120 ms 760 KB Output is correct
23 Correct 121 ms 860 KB Output is correct
24 Correct 120 ms 760 KB Output is correct
25 Correct 120 ms 788 KB Output is correct
26 Correct 120 ms 760 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 630 ms 42388 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 376 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 4 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 760 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 120 ms 760 KB Output is correct
23 Correct 121 ms 860 KB Output is correct
24 Correct 120 ms 760 KB Output is correct
25 Correct 120 ms 788 KB Output is correct
26 Correct 120 ms 760 KB Output is correct
27 Incorrect 26 ms 1784 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 376 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 4 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 760 KB Output is correct
21 Correct 10 ms 760 KB Output is correct
22 Correct 120 ms 760 KB Output is correct
23 Correct 121 ms 860 KB Output is correct
24 Correct 120 ms 760 KB Output is correct
25 Correct 120 ms 788 KB Output is correct
26 Correct 120 ms 760 KB Output is correct
27 Incorrect 691 ms 42352 KB Output isn't correct
28 Halted 0 ms 0 KB -