답안 #49269 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49269	2018-05-24T17:01:17 Z	Kerim	원 고르기 (APIO18_circle_selection)	C++17	19 / 100	1212 ms	43824 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++;
				}
			}
		}	
	}
	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	8 ms	7288 KB	Output is correct
2	Correct	8 ms	7396 KB	Output is correct
3	Correct	8 ms	7472 KB	Output is correct
4	Correct	9 ms	7472 KB	Output is correct
5	Correct	8 ms	7548 KB	Output is correct
6	Correct	8 ms	7548 KB	Output is correct
7	Correct	7 ms	7548 KB	Output is correct
8	Correct	8 ms	7580 KB	Output is correct
9	Correct	8 ms	7580 KB	Output is correct
10	Correct	9 ms	7584 KB	Output is correct
11	Correct	7 ms	7584 KB	Output is correct
12	Correct	8 ms	7660 KB	Output is correct
13	Correct	8 ms	7660 KB	Output is correct
14	Correct	7 ms	7660 KB	Output is correct
15	Correct	7 ms	7660 KB	Output is correct
16	Correct	8 ms	7664 KB	Output is correct
17	Correct	8 ms	7788 KB	Output is correct
18	Correct	10 ms	7788 KB	Output is correct
19	Correct	15 ms	8172 KB	Output is correct
20	Correct	16 ms	8172 KB	Output is correct
21	Correct	19 ms	8188 KB	Output is correct
22	Correct	52 ms	8188 KB	Output is correct
23	Correct	56 ms	8316 KB	Output is correct
24	Correct	51 ms	8316 KB	Output is correct
25	Correct	54 ms	8316 KB	Output is correct
26	Correct	82 ms	8316 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1212 ms	43804 KB	Output is correct
2	Correct	1095 ms	43804 KB	Output is correct
3	Correct	1076 ms	43804 KB	Output is correct
4	Correct	1181 ms	43824 KB	Output is correct
5	Correct	931 ms	43824 KB	Output is correct
6	Correct	966 ms	43824 KB	Output is correct
7	Correct	1012 ms	43824 KB	Output is correct
8	Correct	1068 ms	43824 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	43824 KB	Output is correct
2	Incorrect	201 ms	43824 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7288 KB	Output is correct
2	Correct	8 ms	7396 KB	Output is correct
3	Correct	8 ms	7472 KB	Output is correct
4	Correct	9 ms	7472 KB	Output is correct
5	Correct	8 ms	7548 KB	Output is correct
6	Correct	8 ms	7548 KB	Output is correct
7	Correct	7 ms	7548 KB	Output is correct
8	Correct	8 ms	7580 KB	Output is correct
9	Correct	8 ms	7580 KB	Output is correct
10	Correct	9 ms	7584 KB	Output is correct
11	Correct	7 ms	7584 KB	Output is correct
12	Correct	8 ms	7660 KB	Output is correct
13	Correct	8 ms	7660 KB	Output is correct
14	Correct	7 ms	7660 KB	Output is correct
15	Correct	7 ms	7660 KB	Output is correct
16	Correct	8 ms	7664 KB	Output is correct
17	Correct	8 ms	7788 KB	Output is correct
18	Correct	10 ms	7788 KB	Output is correct
19	Correct	15 ms	8172 KB	Output is correct
20	Correct	16 ms	8172 KB	Output is correct
21	Correct	19 ms	8188 KB	Output is correct
22	Correct	52 ms	8188 KB	Output is correct
23	Correct	56 ms	8316 KB	Output is correct
24	Correct	51 ms	8316 KB	Output is correct
25	Correct	54 ms	8316 KB	Output is correct
26	Correct	82 ms	8316 KB	Output is correct
27	Incorrect	24 ms	43824 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7288 KB	Output is correct
2	Correct	8 ms	7396 KB	Output is correct
3	Correct	8 ms	7472 KB	Output is correct
4	Correct	9 ms	7472 KB	Output is correct
5	Correct	8 ms	7548 KB	Output is correct
6	Correct	8 ms	7548 KB	Output is correct
7	Correct	7 ms	7548 KB	Output is correct
8	Correct	8 ms	7580 KB	Output is correct
9	Correct	8 ms	7580 KB	Output is correct
10	Correct	9 ms	7584 KB	Output is correct
11	Correct	7 ms	7584 KB	Output is correct
12	Correct	8 ms	7660 KB	Output is correct
13	Correct	8 ms	7660 KB	Output is correct
14	Correct	7 ms	7660 KB	Output is correct
15	Correct	7 ms	7660 KB	Output is correct
16	Correct	8 ms	7664 KB	Output is correct
17	Correct	8 ms	7788 KB	Output is correct
18	Correct	10 ms	7788 KB	Output is correct
19	Correct	15 ms	8172 KB	Output is correct
20	Correct	16 ms	8172 KB	Output is correct
21	Correct	19 ms	8188 KB	Output is correct
22	Correct	52 ms	8188 KB	Output is correct
23	Correct	56 ms	8316 KB	Output is correct
24	Correct	51 ms	8316 KB	Output is correct
25	Correct	54 ms	8316 KB	Output is correct
26	Correct	82 ms	8316 KB	Output is correct
27	Correct	1212 ms	43804 KB	Output is correct
28	Correct	1095 ms	43804 KB	Output is correct
29	Correct	1076 ms	43804 KB	Output is correct
30	Correct	1181 ms	43824 KB	Output is correct
31	Correct	931 ms	43824 KB	Output is correct
32	Correct	966 ms	43824 KB	Output is correct
33	Correct	1012 ms	43824 KB	Output is correct
34	Correct	1068 ms	43824 KB	Output is correct
35	Correct	8 ms	43824 KB	Output is correct
36	Incorrect	201 ms	43824 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #49269

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