oj.uz

Submission #57812

# Submission time Handle Problem Language Result Execution time Memory
57812 2018-07-16T09:13:42 Z robert Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 30856 KB 
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

int ans[100100];
pair<ii, int> c[100100];
ii cs[100100];
int act[100100];
int N;

long long pow(long long g, long long e){
	if(e==0){
		return 1;
	} else {
		long long tmp = pow(g, e>>1);
		tmp*=tmp;
		if(e&1)
			tmp *= g;
		return tmp;
	}
}

long long d(int a, int b){
	return pow(c[a].first.second-c[b].first.second, 2)+pow(c[b].first.first-c[a].first.first, 2);
}

void eliminate(int i){
	for(int n=0; n<N; n++){
		if(d(n, i)<=pow(c[n].second+c[i].second, 2)){
		//	cout << i << " " << n << " " << d(n, i) << endl;
			if(act[n]){
				act[n] = 0;
				ans[n] = i;
			}
		}
	}
}

int main(){
	cin>>N;
	for(int n=0; n<N; n++){
		cin>>c[n].first.first>>c[n].first.second>>c[n].second;
		cs[n].first = c[n].second;
		cs[n].second = -n;
		act[n] = 1;
	}
	sort(cs, cs+N);
	reverse(cs, cs+N);
	for(int n=0; n<N; n++){
		//cout << -cs[n].second << endl;
		if(act[-cs[n].second]){
			eliminate(-cs[n].second);
		}
	}
	for(int n=0; n<N; n++){
		if(n)
			cout << " ";
		cout << (ans[n]+1);
	}
	cout << endl;

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 464 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 744 KB Output is correct
6 Correct 3 ms 920 KB Output is correct
7 Correct 3 ms 920 KB Output is correct
8 Correct 2 ms 920 KB Output is correct
9 Correct 3 ms 920 KB Output is correct
10 Correct 3 ms 920 KB Output is correct
11 Correct 3 ms 932 KB Output is correct
12 Correct 3 ms 932 KB Output is correct
13 Correct 3 ms 932 KB Output is correct
14 Correct 3 ms 932 KB Output is correct
15 Correct 3 ms 932 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 932 KB Output is correct
18 Correct 6 ms 976 KB Output is correct
19 Correct 13 ms 1196 KB Output is correct
20 Correct 14 ms 1404 KB Output is correct
21 Correct 16 ms 1492 KB Output is correct
22 Correct 122 ms 1740 KB Output is correct
23 Correct 120 ms 2000 KB Output is correct
24 Correct 131 ms 2148 KB Output is correct
25 Correct 182 ms 2176 KB Output is correct
26 Correct 137 ms 2316 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 10992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10992 KB Output is correct
2 Execution timed out 3030 ms 13740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 17452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 464 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 744 KB Output is correct
6 Correct 3 ms 920 KB Output is correct
7 Correct 3 ms 920 KB Output is correct
8 Correct 2 ms 920 KB Output is correct
9 Correct 3 ms 920 KB Output is correct
10 Correct 3 ms 920 KB Output is correct
11 Correct 3 ms 932 KB Output is correct
12 Correct 3 ms 932 KB Output is correct
13 Correct 3 ms 932 KB Output is correct
14 Correct 3 ms 932 KB Output is correct
15 Correct 3 ms 932 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 932 KB Output is correct
18 Correct 6 ms 976 KB Output is correct
19 Correct 13 ms 1196 KB Output is correct
20 Correct 14 ms 1404 KB Output is correct
21 Correct 16 ms 1492 KB Output is correct
22 Correct 122 ms 1740 KB Output is correct
23 Correct 120 ms 2000 KB Output is correct
24 Correct 131 ms 2148 KB Output is correct
25 Correct 182 ms 2176 KB Output is correct
26 Correct 137 ms 2316 KB Output is correct
27 Correct 28 ms 17452 KB Output is correct
28 Correct 19 ms 17452 KB Output is correct
29 Correct 23 ms 17452 KB Output is correct
30 Correct 414 ms 17452 KB Output is correct
31 Correct 465 ms 17452 KB Output is correct
32 Correct 474 ms 17452 KB Output is correct
33 Correct 185 ms 22840 KB Output is correct
34 Correct 208 ms 25996 KB Output is correct
35 Correct 270 ms 28964 KB Output is correct
36 Execution timed out 3050 ms 30856 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 464 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 744 KB Output is correct
6 Correct 3 ms 920 KB Output is correct
7 Correct 3 ms 920 KB Output is correct
8 Correct 2 ms 920 KB Output is correct
9 Correct 3 ms 920 KB Output is correct
10 Correct 3 ms 920 KB Output is correct
11 Correct 3 ms 932 KB Output is correct
12 Correct 3 ms 932 KB Output is correct
13 Correct 3 ms 932 KB Output is correct
14 Correct 3 ms 932 KB Output is correct
15 Correct 3 ms 932 KB Output is correct
16 Correct 6 ms 932 KB Output is correct
17 Correct 4 ms 932 KB Output is correct
18 Correct 6 ms 976 KB Output is correct
19 Correct 13 ms 1196 KB Output is correct
20 Correct 14 ms 1404 KB Output is correct
21 Correct 16 ms 1492 KB Output is correct
22 Correct 122 ms 1740 KB Output is correct
23 Correct 120 ms 2000 KB Output is correct
24 Correct 131 ms 2148 KB Output is correct
25 Correct 182 ms 2176 KB Output is correct
26 Correct 137 ms 2316 KB Output is correct
27 Runtime error 181 ms 10992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -