oj.uz

Submission #73568

# Submission time Handle Problem Language Result Execution time Memory
73568 2018-08-28T12:54:49 Z KLPP Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 78976 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].second.first=rand()%1000+1;
		//arr[i].second.second=rand()%1000+1;
		//arr[i].first.first=rand()%1000+1;
		arr[i].first.second=-i;
	}
	sort(arr,arr+n);
	reverse(arr,arr+n);
	size=INF;
	int eliminator[n];
	vector<int> v;
	for(int i=0;i<n;i++){//cout<<i<<endl;
		if(!B[i])continue;

		while(size>2*arr[i].first.first){
			rescale();
		}
		//cout<<i<<endl;
		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++){//cout<<i<<endl;
				Range r=grid.equal_range(point(a,b));
				for(mit it=r.first;it!=r.second && it!=grid.end();it++){//cout<<i<<endl;
					//cout<<it->second<<endl;
					int j=it->second;v.push_back(i);
					if(eliminates(i,j) || i==j){
						B[j]=false;
						eliminator[-arr[j].first.second]=-arr[i].first.second;
						mit it2=it;
						grid.erase(it2);
					}
				}
			}
		}
		
		//cout<<i<<endl;
	}
	
	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:70: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 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Incorrect 4 ms 520 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1014 ms 32228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 78976 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 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Incorrect 4 ms 520 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 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 3 ms 484 KB Output is correct
8 Incorrect 4 ms 520 KB Output isn't correct
9 Halted 0 ms 0 KB -