oj.uz

Submission #172309

# Submission time Handle Problem Language Result Execution time Memory
172309 2020-01-01T06:42:48 Z eggag32 Circle selection (APIO18_circle_selection) C++17
7 / 100
 643 ms 42264 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;
					}
					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;
					}
					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

# 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 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 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 4 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 122 ms 760 KB Output is correct
24 Correct 120 ms 788 KB Output is correct
25 Correct 120 ms 792 KB Output is correct
26 Correct 120 ms 888 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 635 ms 42264 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 376 KB Output is correct
2 Incorrect 223 ms 14264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 643 ms 42232 KB Output isn't correct
2 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 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 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 4 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 122 ms 760 KB Output is correct
24 Correct 120 ms 788 KB Output is correct
25 Correct 120 ms 792 KB Output is correct
26 Correct 120 ms 888 KB Output is correct
27 Incorrect 22 ms 1784 KB Output isn't correct
28 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 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 3 ms 376 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 4 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 122 ms 760 KB Output is correct
24 Correct 120 ms 788 KB Output is correct
25 Correct 120 ms 792 KB Output is correct
26 Correct 120 ms 888 KB Output is correct
27 Incorrect 635 ms 42264 KB Output isn't correct
28 Halted 0 ms 0 KB -