oj.uz

답안 #49270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49270 2018-05-24T17:07:58 Z Kerim 원 고르기 (APIO18_circle_selection) C++17
23 / 100
 2059 ms 80448 KB 
#include "bits/stdc++.h"
#define MAXN 300009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
pair<PII,PII>arr[MAXN];
bool cmp(pair<PII,PII>x,pair<PII,PII>y){
	if(x.ff.ff!=y.ff.ff)
		return (x.ff.ff>y.ff.ff);
	return (x.ff.ss<y.ff.ss);	
}
int ans[MAXN],id[MAXN];
ll sqr(int x){
	return x*1LL*x;
}
ll dis(PII x,PII y){
	return sqr(x.ff-y.ff)+sqr(x.ss-y.ss);
}
set<PII>s;
map<int,int>pm;
vector<PII>adj[MAXN];
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,all=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
		int x,y,r;
		scanf("%d%d%d",&x,&y,&r);
		arr[i]=mp(mp(r,i),mp(x,y));
		s.insert(mp(x-r,i));
		all+=(!y);
		s.insert(mp(x+r,i));
	}
	sort(arr+1,arr+n+1,cmp);
	if(n<=5000 and 1==0){//1st subtask
		for(int i=1;i<=n;i++){
			if(ans[arr[i].ff.ss])
				continue;
			for(int j=i;j<=n;j++)
				if(!ans[arr[j].ff.ss] and dis(arr[i].ss,arr[j].ss)<=sqr(arr[i].ff.ff+arr[j].ff.ff))
					ans[arr[j].ff.ss]=arr[i].ff.ss;
		}
	}
	else if(all==n and 1==0){//2nd subtask
		for(int i=1;i<=n;i++){
			int x=arr[i].ss.ff;
			int r=arr[i].ff.ff;
			int ind=arr[i].ff.ss;
			if(ans[ind])
				continue;
			ans[ind]=ind;	
			s.erase(mp(x+r,ind));
			s.erase(mp(x-r,ind));
			__typeof((s).begin())it=s.lower_bound(mp(x-r,-1));
			while(it!=s.end()){
				if(abs(it->ff-x)>r)
					break;
				if(!ans[it->ss])
					ans[it->ss]=ind;
				s.erase(it++);	
			}
		}
	}
	else if(arr[1].ff.ff==arr[n].ff.ff){//3rd subtask
		int r=arr[1].ff.ff;
		for(int i=1;i<=n;i++)
			pm[arr[i].ss.ff/r]=1;
		int c=0;
		tr(it,pm){
			it->ss=++c;
			id[c]=it->ff;
		}
		for(int i=1;i<=n;i++)
			adj[pm[arr[i].ss.ff/r]].pb(mp(arr[i].ss.ss/r,arr[i].ff.ss));
		for(int i=1;i<=c;i++)
			sort(all(adj[i]));
		for(int i=1;i<=n;i++){
			int x=arr[i].ss.ff;
			int y=arr[i].ss.ss;
			int ind=arr[i].ff.ss;
			if(ans[ind])
				continue;
			for(int j=max(1,pm[x/r]-2);j<=min(c,pm[x/r]+2);j++){
				if(abs(id[j]-x/r)>2)
					continue;
				int pos=lower_bound(all(adj[j]),mp(y/r-2,-1))-adj[j].begin();
				while(pos<int(adj[j].size()) and adj[j][pos].ff<=y/r+2){
					int new_ind=adj[j][pos].ss;
					if(!ans[new_ind] and dis(arr[ind].ss,arr[new_ind].ss)<=sqr(2*r))
						ans[new_ind]=ind;
					pos++;
				}
			}
		}	
	}
	else
		assert(0);
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);;
	puts("");	
	return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Runtime error 15 ms 14692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 935 ms 80448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 80448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1669 ms 80448 KB Output is correct
2 Correct 1822 ms 80448 KB Output is correct
3 Correct 984 ms 80448 KB Output is correct
4 Correct 1921 ms 80448 KB Output is correct
5 Correct 2059 ms 80448 KB Output is correct
6 Correct 1081 ms 80448 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Runtime error 15 ms 14692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Runtime error 15 ms 14692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -