oj.uz

Submission #73531

# Submission time Handle Problem Language Result Execution time Memory
73531 2018-08-28T11:41:18 Z KLPP Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 44140 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
#define INF 4000000000
typedef long long int lld;
typedef pair<lld,lld> point;
typedef pair<pair<lld,int>,point> circle;
typedef std::multimap<point,int>::iterator mit;
typedef pair<mit,mit> Range;
 
multimap<point,int> grid;
lld size;
bool B[400000];
circle arr[400000];
int n;
void rescale(){
	size++;
	size/=2;
	grid.clear();
	for(int i=0;i<n;i++){
		if(B[i]){
			point center=arr[i].second;
			center.first/=size;
			center.second/=size;
			grid.insert(pair<point,int>(center,i));
		}
	}
}
lld sq(lld x){
	return x*x;
}
bool eliminates(int i, int j){
	if(sq(arr[i].first.first+arr[j].first.first)>=sq(arr[i].second.first-arr[j].second.first)+sq(arr[i].second.second-arr[j].second.second)){
		return true;
	}return false;
}
void print(){
	for(int i=0;i<n;i++){
		point center=arr[i].second;
		center.first/=size;
		center.second/=size;
		cout<<center.first<<" "<<center.second<<endl;
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){B[i]=true;
		cin>>arr[i].second.first>>arr[i].second.second>>arr[i].first.first;
		arr[i].first.second=-i;
	}
	sort(arr,arr+n);
	reverse(arr,arr+n);
	size=INF;
	int eliminator[n];
	for(int i=0;i<n;i++){
		if(!B[i])continue;

		while(size>2*arr[i].first.first){
			rescale();
		}
		
		int index=-arr[i].first.second;
		lld xgrid=arr[i].second.first/size;
		lld ygrid=arr[i].second.second/size;

		for(lld a=xgrid-2;a<=xgrid+2;a++){
			for(lld b=ygrid-2;b<=ygrid+2;b++){

				Range r=grid.equal_range(point(a,b));
				for(mit it=r.first;it!=r.second;it++){
					int j=it->second;

					if(eliminates(i,j) || i==j){
						
						B[j]=false;
						eliminator[-arr[j].first.second]=-arr[i].first.second;
						mit it2=it;
						grid.erase(it2);
					}
				}
			}
		}
	}
	
	for(int i=0;i<n;i++)cout<<eliminator[i]+1<<" ";
	cout<<endl;
	return 0;	
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:66:7: warning: unused variable 'index' [-Wunused-variable]
   int index=-arr[i].first.second;
       ^~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 628 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Incorrect 4 ms 636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3017 ms 37172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 44140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 628 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Incorrect 4 ms 636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 628 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Incorrect 4 ms 636 KB Output isn't correct
9 Halted 0 ms 0 KB -