답안 #49267 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49267	2018-05-24T16:56:16 Z	Kerim	원 고르기 (APIO18_circle_selection)	C++17	19 / 100	1223 ms	58776 KB

circle_selection

#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){//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){//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
		wr
		exit(0);
		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
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7380 KB	Output is correct
2	Correct	8 ms	7380 KB	Output is correct
3	Correct	8 ms	7452 KB	Output is correct
4	Correct	7 ms	7536 KB	Output is correct
5	Correct	7 ms	7536 KB	Output is correct
6	Correct	8 ms	7588 KB	Output is correct
7	Correct	10 ms	7664 KB	Output is correct
8	Correct	7 ms	7676 KB	Output is correct
9	Correct	7 ms	7676 KB	Output is correct
10	Correct	9 ms	7676 KB	Output is correct
11	Correct	10 ms	7676 KB	Output is correct
12	Correct	9 ms	7676 KB	Output is correct
13	Correct	7 ms	7680 KB	Output is correct
14	Correct	7 ms	7680 KB	Output is correct
15	Correct	7 ms	7680 KB	Output is correct
16	Correct	8 ms	7680 KB	Output is correct
17	Correct	11 ms	7680 KB	Output is correct
18	Correct	9 ms	7680 KB	Output is correct
19	Correct	15 ms	8188 KB	Output is correct
20	Correct	18 ms	8188 KB	Output is correct
21	Correct	16 ms	8204 KB	Output is correct
22	Correct	54 ms	8280 KB	Output is correct
23	Correct	51 ms	8280 KB	Output is correct
24	Correct	54 ms	8280 KB	Output is correct
25	Correct	50 ms	8300 KB	Output is correct
26	Correct	50 ms	8300 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1038 ms	43712 KB	Output is correct
2	Correct	1156 ms	43816 KB	Output is correct
3	Correct	914 ms	43816 KB	Output is correct
4	Correct	1030 ms	43816 KB	Output is correct
5	Correct	1223 ms	43816 KB	Output is correct
6	Correct	930 ms	43816 KB	Output is correct
7	Correct	955 ms	43816 KB	Output is correct
8	Correct	902 ms	43816 KB	Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	666 ms	58776 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7380 KB	Output is correct
2	Correct	8 ms	7380 KB	Output is correct
3	Correct	8 ms	7452 KB	Output is correct
4	Correct	7 ms	7536 KB	Output is correct
5	Correct	7 ms	7536 KB	Output is correct
6	Correct	8 ms	7588 KB	Output is correct
7	Correct	10 ms	7664 KB	Output is correct
8	Correct	7 ms	7676 KB	Output is correct
9	Correct	7 ms	7676 KB	Output is correct
10	Correct	9 ms	7676 KB	Output is correct
11	Correct	10 ms	7676 KB	Output is correct
12	Correct	9 ms	7676 KB	Output is correct
13	Correct	7 ms	7680 KB	Output is correct
14	Correct	7 ms	7680 KB	Output is correct
15	Correct	7 ms	7680 KB	Output is correct
16	Correct	8 ms	7680 KB	Output is correct
17	Correct	11 ms	7680 KB	Output is correct
18	Correct	9 ms	7680 KB	Output is correct
19	Correct	15 ms	8188 KB	Output is correct
20	Correct	18 ms	8188 KB	Output is correct
21	Correct	16 ms	8204 KB	Output is correct
22	Correct	54 ms	8280 KB	Output is correct
23	Correct	51 ms	8280 KB	Output is correct
24	Correct	54 ms	8280 KB	Output is correct
25	Correct	50 ms	8300 KB	Output is correct
26	Correct	50 ms	8300 KB	Output is correct
27	Runtime error	29 ms	58776 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7380 KB	Output is correct
2	Correct	8 ms	7380 KB	Output is correct
3	Correct	8 ms	7452 KB	Output is correct
4	Correct	7 ms	7536 KB	Output is correct
5	Correct	7 ms	7536 KB	Output is correct
6	Correct	8 ms	7588 KB	Output is correct
7	Correct	10 ms	7664 KB	Output is correct
8	Correct	7 ms	7676 KB	Output is correct
9	Correct	7 ms	7676 KB	Output is correct
10	Correct	9 ms	7676 KB	Output is correct
11	Correct	10 ms	7676 KB	Output is correct
12	Correct	9 ms	7676 KB	Output is correct
13	Correct	7 ms	7680 KB	Output is correct
14	Correct	7 ms	7680 KB	Output is correct
15	Correct	7 ms	7680 KB	Output is correct
16	Correct	8 ms	7680 KB	Output is correct
17	Correct	11 ms	7680 KB	Output is correct
18	Correct	9 ms	7680 KB	Output is correct
19	Correct	15 ms	8188 KB	Output is correct
20	Correct	18 ms	8188 KB	Output is correct
21	Correct	16 ms	8204 KB	Output is correct
22	Correct	54 ms	8280 KB	Output is correct
23	Correct	51 ms	8280 KB	Output is correct
24	Correct	54 ms	8280 KB	Output is correct
25	Correct	50 ms	8300 KB	Output is correct
26	Correct	50 ms	8300 KB	Output is correct
27	Correct	1038 ms	43712 KB	Output is correct
28	Correct	1156 ms	43816 KB	Output is correct
29	Correct	914 ms	43816 KB	Output is correct
30	Correct	1030 ms	43816 KB	Output is correct
31	Correct	1223 ms	43816 KB	Output is correct
32	Correct	930 ms	43816 KB	Output is correct
33	Correct	955 ms	43816 KB	Output is correct
34	Correct	902 ms	43816 KB	Output is correct
35	Correct	7 ms	43816 KB	Output is correct
36	Runtime error	186 ms	43816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Halted	0 ms	0 KB	-

답안 #49267

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0