Submission #497616

#	Time	Username	Problem	Language	Result	Execution time	Memory
497616		jamezzz	Circle selection (APIO18_circle_selection)	C++17	100 / 100	994 ms	48980 KiB

circle_selection

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
    int x=0;
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9')ch=getchar_unlocked();
    while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar_unlocked();
	}
    return x;
}

#define maxn 300005

struct circle{
	ll x,y,r,i;
}a[maxn];

bool cmp(circle &a,circle &b){
	if(a.r==b.r)return a.i<b.i;
	return a.r>b.r;
}

bool intersect(circle &i,circle &j){
	return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y)<=(i.r+j.r)*(i.r+j.r);
}

int n;ll x,y,r,ans[maxn];
bool used[maxn];
ll gridsz;
unordered_map<ll,vector<int>> grid;

ll hh(ll x,ll y){
	return x*(1ll<<32)+y;
}

void build(){
	grid.clear();
	for(int i=1;i<=n;++i){
		if(used[i])continue;
		ll x=a[i].x/gridsz;
		ll y=a[i].y/gridsz;
		grid[hh(x,y)].pb(i);
	}
}

int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		sf("%lld%lld%lld",&x,&y,&r);
		x+=(1ll<<30);y+=(1ll<<30);
		a[i]={x,y,r,i};
		mxto(gridsz,r);
	}
	sort(a+1,a+n+1,cmp);
	build();
	for(int i=1;i<=n;++i){
		if(used[i])continue;
		if(gridsz>2*a[i].r){
			gridsz=a[i].r;
			build();
		}
		ll x=a[i].x/gridsz;
		ll y=a[i].y/gridsz;
		for(ll nx=x-2;nx<=x+2;++nx){
			for(ll ny=y-2;ny<=y+2;++ny){
				if(grid.find(hh(nx,ny))==grid.end())continue;
				vector<int> tmp;
				vector<int> &pts=grid[hh(nx,ny)];
				for(int p:pts){
					if(intersect(a[i],a[p])){
						used[p]=true;
						ans[a[p].i]=a[i].i;
					}
					else tmp.pb(p);
				}
				swap(grid[hh(nx,ny)],tmp);
			}
		}
	}
	for(int i=1;i<=n;++i)pf("%d ",ans[i]);
	pf("\n");
}

/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:123:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
  123 |  for(int i=1;i<=n;++i)pf("%d ",ans[i]);
      |                           ~^   ~~~~~~
      |                            |        |
      |                            int      ll {aka long long int}
      |                           %lld
circle_selection.cpp:90:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  sf("%d",&n);
      |    ^
circle_selection.cpp:92:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   sf("%lld%lld%lld",&x,&y,&r);
      |     ^

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