oj.uz

Submission #99825

# Submission time Handle Problem Language Result Execution time Memory
99825 2019-03-07T16:44:41 Z TadijaSebez Circle selection (APIO18_circle_selection) C++11
0 / 100
 246 ms 57368 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
struct circle{ ll x,y,r;int id;circle(){}circle(ll a, ll b, ll c):x(a),y(b),r(c){}};
ll sq(ll x){ return x*x;}
bool sec(circle a, circle b){ return sq(a.x-b.x)+sq(a.y-b.y)<=sq(a.r+b.r);}
bool operator < (circle a, circle b){ return 1;}
const int N=300050;
const ll mul=2e9+7;
circle a[N];
int ans[N];
unordered_map<ll,int> id;
vector<pair<int,circle>> all[N];
int main()
{
	int n,i;
	scanf("%i",&n);
	for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i;
	sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
	for(int j=30;j>=0;j--)
	{
		int po=1<<j;
		id.clear();
		int cnt=0;
		for(i=1;i<=n;i++) if(!ans[a[i].id])
		{
			pair<int,int> pa=mp(floor((double)a[i].x/po),floor((double)a[i].y/po));
			ll p=pa.first;
			if(!id[p]) id[p]=++cnt,all[cnt].clear();
			all[id[p]].pb(mp(pa.second,a[i]));
		}
		for(i=1;i<=cnt;i++) sort(all[i].begin(),all[i].end());
		for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
		{
			int x=floor((double)a[i].x/po);
			int y=floor((double)a[i].y/po);
			for(int l=-2;l<=2;l++)
			{
				ll p=x+l;
				if(!id.count(p)) continue;
				int idx=id[p];
				int lb=upper_bound(all[idx].begin(),all[idx].end(),mp(y-3,a[i]))-all[idx].begin();
				int rb=upper_bound(all[idx].begin(),all[idx].end(),mp(y+2,a[i]))-all[idx].begin();
				for(int r=lb;r<rb;r++)
				{
					circle c=all[idx][r].second;
					if(!ans[c.id] && sec(c,a[i])) ans[c.id]=a[i].id;
				}
			}
		}
	}
	for(i=1;i<=n;i++) printf("%i%c",ans[i],i==n?'\n':' ');
	return 0;
}

Compilation message

circle_selection.cpp: In lambda function:
circle_selection.cpp:21:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
                                                           ~~~~~~~~~^~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:35:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
                                                     ~^~
circle_selection.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:20:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i;
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Runtime error 21 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 231 ms 57368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Runtime error 100 ms 28936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 246 ms 57232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Runtime error 21 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Runtime error 21 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -