제출 #99833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99833		TadijaSebez	원 고르기 (APIO18_circle_selection)	C++11	64 / 100	3067 ms	73180 KiB

circle_selection

#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 a.r<b.r;}
const int N=300050;
const int mul=2e9+7;
circle a[N],b[N];
int ans[N];
unordered_map<ll,int> id;
vector<pair<int,int>> 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,b[i]=a[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].id));
   		}
   		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,mul))-all[idx].begin();
   				//int rb=upper_bound(all[idx].begin(),all[idx].end(),mp(y+2,mul))-all[idx].begin();
   				for(int r=lb;r<all[idx].size() && all[idx][r]<=mp(y+2,mul);r++)
   				{
   					int c=all[idx][r].second;
   					if(!ans[c] && sec(b[c],a[i])) ans[c]=a[i].id;
   				}
   			}
   		}
   	}
   	for(i=1;i<=n;i++) printf("%i%c",ans[i],i==n?'\n':' ');
   	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In lambda function:
circle_selection.cpp:21:71: 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:57: 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:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int r=lb;r<all[idx].size() && all[idx][r]<=mp(y+2,mul);r++)
                     ~^~~~~~~~~~~~~~~~
circle_selection.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:20:80: 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,b[i]=a[i];
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13