답안 #64374 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64374	2018-08-04T08:59:57 Z	zscoder	원 고르기 (APIO18_circle_selection)	C++17	64 / 100	3000 ms	152676 KB

circle_selection

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct circle
{
	int x,y,r,id;
	circle(int _x, int _y, int _r, int _id){x=_x;y=_y;r=_r;id=_id;}
};

bool operator<(circle a, circle b)
{
	if(a.r!=b.r) return a.r<b.r;
	else return a.id>b.id;
}

vector<circle> a;
int ans[333333];
vector<circle> vec;

vector<pair<int,int> > V[333333];
vi xs;

void init(int R)
{
	xs.clear();
	for(int i=0;i<vec.size();i++)
	{
		if(!ans[vec[i].id])
		{
			xs.pb(vec[i].x/R);
		}
	}
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for(int i=0;i<xs.size();i++) V[i].clear();
	for(int i=0;i<vec.size();i++)
	{
		if(!ans[vec[i].id])
		{
			V[lower_bound(xs.begin(),xs.end(),vec[i].x/R)-xs.begin()].pb(mp(vec[i].y/R, vec[i].id));
		}
	}
	for(int i=0;i<xs.size();i++) sort(V[i].begin(),V[i].end());
}

bool intersect(circle x, circle y)
{
	ll d = (x.x-y.x)*1LL*(x.x-y.x) + (x.y-y.y)*1LL*(x.y-y.y);
	return (d<=(x.r+y.r)*1LL*(x.r+y.r));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		int x,y,r; cin>>x>>y>>r;
		vec.pb(circle(x,y,r,i+1));
	}
	a=vec;
	sort(vec.rbegin(),vec.rend());
	int curC = int(1e9); init(curC);
	for(int i=0;i<vec.size();i++)
	{
		if(ans[vec[i].id]) continue;
		while(vec[i].r*2<curC)
		{
			curC/=2; init(curC);
		}
		int x=vec[i].x/curC;
		x=lower_bound(xs.begin(),xs.end(),x)-xs.begin();
		for(int dx=-2;dx<=2;dx++)
		{
			if(x+dx>=0&&x+dx<xs.size()&&abs(xs[x]-xs[x+dx])<=2)
			{
				auto it = lower_bound(V[x+dx].begin(),V[x+dx].end(),mp(vec[i].y/curC - 2, -1));
				for(;it!=V[x+dx].end()&&it->fi<=vec[i].y/curC + 2;it++)
				{
					if(ans[it->se]){continue;}
					if(intersect(a[it->se-1], vec[i]))
					{
						ans[it->se] = vec[i].id; 
					}
				} 
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i];
		if(i+1<=n) cout<<' ';
	}
	cout<<'\n';
}

Compilation message

circle_selection.cpp: In function 'void init(int)':
circle_selection.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<xs.size();i++) V[i].clear();
              ~^~~~~~~~~~
circle_selection.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<xs.size();i++) sort(V[i].begin(),V[i].end());
              ~^~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(x+dx>=0&&x+dx<xs.size()&&abs(xs[x]-xs[x+dx])<=2)
                ~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	8172 KB	Output is correct
2	Correct	14 ms	8300 KB	Output is correct
3	Correct	14 ms	8300 KB	Output is correct
4	Correct	15 ms	8392 KB	Output is correct
5	Correct	11 ms	8392 KB	Output is correct
6	Correct	13 ms	8392 KB	Output is correct
7	Correct	13 ms	8392 KB	Output is correct
8	Correct	13 ms	8392 KB	Output is correct
9	Correct	12 ms	8392 KB	Output is correct
10	Correct	11 ms	8392 KB	Output is correct
11	Correct	12 ms	8444 KB	Output is correct
12	Correct	11 ms	8448 KB	Output is correct
13	Correct	12 ms	8496 KB	Output is correct
14	Correct	10 ms	8496 KB	Output is correct
15	Correct	10 ms	8528 KB	Output is correct
16	Correct	13 ms	8664 KB	Output is correct
17	Correct	15 ms	8664 KB	Output is correct
18	Correct	11 ms	8664 KB	Output is correct
19	Correct	19 ms	9096 KB	Output is correct
20	Correct	15 ms	9248 KB	Output is correct
21	Correct	15 ms	9352 KB	Output is correct
22	Correct	34 ms	9568 KB	Output is correct
23	Correct	34 ms	9648 KB	Output is correct
24	Correct	31 ms	9648 KB	Output is correct
25	Correct	37 ms	9648 KB	Output is correct
26	Correct	37 ms	9716 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	376 ms	30820 KB	Output is correct
2	Correct	413 ms	37476 KB	Output is correct
3	Correct	472 ms	43856 KB	Output is correct
4	Correct	303 ms	50908 KB	Output is correct
5	Correct	1602 ms	71088 KB	Output is correct
6	Correct	2093 ms	87604 KB	Output is correct
7	Correct	1596 ms	87604 KB	Output is correct
8	Correct	1657 ms	93552 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	93552 KB	Output is correct
2	Correct	461 ms	93552 KB	Output is correct
3	Correct	1718 ms	93552 KB	Output is correct
4	Correct	1844 ms	101076 KB	Output is correct
5	Correct	1633 ms	104116 KB	Output is correct
6	Correct	779 ms	104116 KB	Output is correct
7	Correct	392 ms	104116 KB	Output is correct
8	Correct	85 ms	104116 KB	Output is correct
9	Correct	1961 ms	122956 KB	Output is correct
10	Correct	1301 ms	123796 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	8172 KB	Output is correct
2	Correct	14 ms	8300 KB	Output is correct
3	Correct	14 ms	8300 KB	Output is correct
4	Correct	15 ms	8392 KB	Output is correct
5	Correct	11 ms	8392 KB	Output is correct
6	Correct	13 ms	8392 KB	Output is correct
7	Correct	13 ms	8392 KB	Output is correct
8	Correct	13 ms	8392 KB	Output is correct
9	Correct	12 ms	8392 KB	Output is correct
10	Correct	11 ms	8392 KB	Output is correct
11	Correct	12 ms	8444 KB	Output is correct
12	Correct	11 ms	8448 KB	Output is correct
13	Correct	12 ms	8496 KB	Output is correct
14	Correct	10 ms	8496 KB	Output is correct
15	Correct	10 ms	8528 KB	Output is correct
16	Correct	13 ms	8664 KB	Output is correct
17	Correct	15 ms	8664 KB	Output is correct
18	Correct	11 ms	8664 KB	Output is correct
19	Correct	19 ms	9096 KB	Output is correct
20	Correct	15 ms	9248 KB	Output is correct
21	Correct	15 ms	9352 KB	Output is correct
22	Correct	34 ms	9568 KB	Output is correct
23	Correct	34 ms	9648 KB	Output is correct
24	Correct	31 ms	9648 KB	Output is correct
25	Correct	37 ms	9648 KB	Output is correct
26	Correct	37 ms	9716 KB	Output is correct
27	Correct	23 ms	141348 KB	Output is correct
28	Correct	26 ms	141348 KB	Output is correct
29	Correct	20 ms	141348 KB	Output is correct
30	Correct	60 ms	141348 KB	Output is correct
31	Correct	49 ms	141348 KB	Output is correct
32	Correct	63 ms	141348 KB	Output is correct
33	Correct	107 ms	141348 KB	Output is correct
34	Correct	119 ms	141348 KB	Output is correct
35	Correct	154 ms	141348 KB	Output is correct
36	Correct	678 ms	141348 KB	Output is correct
37	Correct	628 ms	141348 KB	Output is correct
38	Correct	517 ms	141348 KB	Output is correct
39	Correct	732 ms	141348 KB	Output is correct
40	Correct	772 ms	141348 KB	Output is correct
41	Correct	657 ms	141348 KB	Output is correct
42	Correct	370 ms	141348 KB	Output is correct
43	Correct	705 ms	141348 KB	Output is correct
44	Correct	674 ms	141348 KB	Output is correct
45	Correct	653 ms	141348 KB	Output is correct
46	Correct	725 ms	141932 KB	Output is correct
47	Correct	656 ms	145064 KB	Output is correct
48	Correct	638 ms	147420 KB	Output is correct
49	Correct	745 ms	149964 KB	Output is correct
50	Correct	748 ms	152676 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	8172 KB	Output is correct
2	Correct	14 ms	8300 KB	Output is correct
3	Correct	14 ms	8300 KB	Output is correct
4	Correct	15 ms	8392 KB	Output is correct
5	Correct	11 ms	8392 KB	Output is correct
6	Correct	13 ms	8392 KB	Output is correct
7	Correct	13 ms	8392 KB	Output is correct
8	Correct	13 ms	8392 KB	Output is correct
9	Correct	12 ms	8392 KB	Output is correct
10	Correct	11 ms	8392 KB	Output is correct
11	Correct	12 ms	8444 KB	Output is correct
12	Correct	11 ms	8448 KB	Output is correct
13	Correct	12 ms	8496 KB	Output is correct
14	Correct	10 ms	8496 KB	Output is correct
15	Correct	10 ms	8528 KB	Output is correct
16	Correct	13 ms	8664 KB	Output is correct
17	Correct	15 ms	8664 KB	Output is correct
18	Correct	11 ms	8664 KB	Output is correct
19	Correct	19 ms	9096 KB	Output is correct
20	Correct	15 ms	9248 KB	Output is correct
21	Correct	15 ms	9352 KB	Output is correct
22	Correct	34 ms	9568 KB	Output is correct
23	Correct	34 ms	9648 KB	Output is correct
24	Correct	31 ms	9648 KB	Output is correct
25	Correct	37 ms	9648 KB	Output is correct
26	Correct	37 ms	9716 KB	Output is correct
27	Correct	376 ms	30820 KB	Output is correct
28	Correct	413 ms	37476 KB	Output is correct
29	Correct	472 ms	43856 KB	Output is correct
30	Correct	303 ms	50908 KB	Output is correct
31	Correct	1602 ms	71088 KB	Output is correct
32	Correct	2093 ms	87604 KB	Output is correct
33	Correct	1596 ms	87604 KB	Output is correct
34	Correct	1657 ms	93552 KB	Output is correct
35	Correct	10 ms	93552 KB	Output is correct
36	Correct	461 ms	93552 KB	Output is correct
37	Correct	1718 ms	93552 KB	Output is correct
38	Correct	1844 ms	101076 KB	Output is correct
39	Correct	1633 ms	104116 KB	Output is correct
40	Correct	779 ms	104116 KB	Output is correct
41	Correct	392 ms	104116 KB	Output is correct
42	Correct	85 ms	104116 KB	Output is correct
43	Correct	1961 ms	122956 KB	Output is correct
44	Correct	1301 ms	123796 KB	Output is correct
45	Correct	1733 ms	131636 KB	Output is correct
46	Execution timed out	3042 ms	141348 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

답안 #64374

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0