oj.uz

Submission #64374

# Submission time Handle Problem Language Result Execution time Memory
64374 2018-08-04T08:59:57 Z zscoder Circle selection (APIO18_circle_selection) C++17
64 / 100
 3000 ms 152676 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -