답안 #835551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835551	2023-08-23T15:40:45 Z	jamielim	원 고르기 (APIO18_circle_selection)	C++14	7 / 100	3000 ms	35500 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n;
i4 arr[300005];
int ans[300005];
set<i4> pq;
int scale=(1<<31);
map<ii,vector<int> > m;

inline void downscale(){
	scale/=2;
	m.clear();
	for(i4 i:pq){
		m[mp(i.se.fi/scale,i.se.se/scale)].pb(-i.fi.se);
	}
}

inline bool intersect(int a,int b){
	ll dx=arr[a].se.fi-arr[b].se.fi;
	ll dy=arr[a].se.se-arr[b].se.se;
	ll r=arr[a].fi.fi+arr[b].fi.fi;
	return (dx*dx<=r*r-dy*dy);
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&arr[i].se.fi,&arr[i].se.se,&arr[i].fi.fi);
		arr[i].se.fi+=INF;arr[i].se.se+=INF;
		arr[i].fi.se=-i;
		pq.insert(arr[i]);
	}
	memset(ans,-1,sizeof(ans));
	downscale();
	while(!pq.empty()){
		auto it=pq.end();--it;
		i4 cur=(*it);pq.erase(it);
		int index=-cur.fi.se;
		if(ans[index]!=-1)continue;
		ans[index]=index;
		while(scale>cur.fi.fi){
			downscale();
		}
		int x=cur.se.fi/scale,y=cur.se.se/scale;
		for(int i=x-2;i<=x+2;i++){
			for(int j=y-2;j<=y+2;j++){
				vector<int> v1=m[mp(i,j)];
				vector<int> v2;
				for(int k:v1){
					if(intersect(k,index)){
						i4 link=arr[k];
						pq.erase(link);
						ans[k]=index;
					}else{
						v2.pb(k);
					}
				}
				swap(m[mp(i,j)],v2);
			}
		}
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]+1);
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
circle_selection.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d%d%d",&arr[i].se.fi,&arr[i].se.se,&arr[i].fi.fi);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1492 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1364 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1492 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1492 KB	Output is correct
11	Correct	1 ms	1492 KB	Output is correct
12	Correct	1 ms	1492 KB	Output is correct
13	Correct	1 ms	1492 KB	Output is correct
14	Correct	1 ms	1492 KB	Output is correct
15	Correct	1 ms	1492 KB	Output is correct
16	Correct	1 ms	1492 KB	Output is correct
17	Correct	1 ms	1492 KB	Output is correct
18	Correct	1 ms	1492 KB	Output is correct
19	Correct	5 ms	2088 KB	Output is correct
20	Correct	4 ms	2004 KB	Output is correct
21	Correct	4 ms	2024 KB	Output is correct
22	Correct	45 ms	2140 KB	Output is correct
23	Correct	47 ms	2140 KB	Output is correct
24	Correct	48 ms	2148 KB	Output is correct
25	Correct	53 ms	2080 KB	Output is correct
26	Correct	56 ms	2076 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	332 ms	27868 KB	Output is correct
2	Correct	329 ms	28228 KB	Output is correct
3	Correct	360 ms	34236 KB	Output is correct
4	Correct	318 ms	34188 KB	Output is correct
5	Correct	2481 ms	35500 KB	Output is correct
6	Execution timed out	3071 ms	35368 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1364 KB	Output is correct
2	Execution timed out	3075 ms	10404 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3042 ms	30176 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1492 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1364 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1492 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1492 KB	Output is correct
11	Correct	1 ms	1492 KB	Output is correct
12	Correct	1 ms	1492 KB	Output is correct
13	Correct	1 ms	1492 KB	Output is correct
14	Correct	1 ms	1492 KB	Output is correct
15	Correct	1 ms	1492 KB	Output is correct
16	Correct	1 ms	1492 KB	Output is correct
17	Correct	1 ms	1492 KB	Output is correct
18	Correct	1 ms	1492 KB	Output is correct
19	Correct	5 ms	2088 KB	Output is correct
20	Correct	4 ms	2004 KB	Output is correct
21	Correct	4 ms	2024 KB	Output is correct
22	Correct	45 ms	2140 KB	Output is correct
23	Correct	47 ms	2140 KB	Output is correct
24	Correct	48 ms	2148 KB	Output is correct
25	Correct	53 ms	2080 KB	Output is correct
26	Correct	56 ms	2076 KB	Output is correct
27	Correct	7 ms	2620 KB	Output is correct
28	Correct	7 ms	2620 KB	Output is correct
29	Correct	7 ms	2688 KB	Output is correct
30	Correct	169 ms	2748 KB	Output is correct
31	Correct	169 ms	2780 KB	Output is correct
32	Correct	170 ms	2772 KB	Output is correct
33	Correct	87 ms	13228 KB	Output is correct
34	Correct	77 ms	13312 KB	Output is correct
35	Correct	76 ms	13108 KB	Output is correct
36	Execution timed out	3062 ms	13660 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1492 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1364 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1492 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1492 KB	Output is correct
11	Correct	1 ms	1492 KB	Output is correct
12	Correct	1 ms	1492 KB	Output is correct
13	Correct	1 ms	1492 KB	Output is correct
14	Correct	1 ms	1492 KB	Output is correct
15	Correct	1 ms	1492 KB	Output is correct
16	Correct	1 ms	1492 KB	Output is correct
17	Correct	1 ms	1492 KB	Output is correct
18	Correct	1 ms	1492 KB	Output is correct
19	Correct	5 ms	2088 KB	Output is correct
20	Correct	4 ms	2004 KB	Output is correct
21	Correct	4 ms	2024 KB	Output is correct
22	Correct	45 ms	2140 KB	Output is correct
23	Correct	47 ms	2140 KB	Output is correct
24	Correct	48 ms	2148 KB	Output is correct
25	Correct	53 ms	2080 KB	Output is correct
26	Correct	56 ms	2076 KB	Output is correct
27	Correct	332 ms	27868 KB	Output is correct
28	Correct	329 ms	28228 KB	Output is correct
29	Correct	360 ms	34236 KB	Output is correct
30	Correct	318 ms	34188 KB	Output is correct
31	Correct	2481 ms	35500 KB	Output is correct
32	Execution timed out	3071 ms	35368 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-

답안 #835551

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 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
0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0