Submission #51096

#	Time	Username	Problem	Language	Result	Execution time	Memory
51096		boook	Circle selection (APIO18_circle_selection)	C++14	57 / 100	3059 ms	63168 KiB

circle_selection

/*input
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
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 300090
#define getchar getchar_unlocked
#define INF 2e9

gp_hash_table<int_fast64_t , int> cc;

vector<PII> v[MAX];
vector<int> las;
int_fast64_t R = 1e14;
int n , pos;
int x[MAX] , y[MAX] , r[MAX] , sol[MAX] , ans[MAX];
inline int_fast64_t trs(int a , int b){ return 1LL * a * 1000000009 + b; }
inline int cmp(int a , int b){ return mp(r[a] , -a) > mp(r[b] , -b); }
inline int tch(int a , int b){
	int_fast64_t val = 1LL * (x[a] - x[b]) * (x[a] - x[b]) + 1LL * (y[a] - y[b]) * (y[a] - y[b]);
	return (val <= 1LL * (r[a] + r[b]) * (r[a] + r[b]));
}
inline int rit(){
	int val = 0 , f = 1;
	char c = getchar();
	while(!isdigit(c)){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(isdigit(c)){
		val = (val << 1) + (val << 3) + c - '0';
		c = getchar();
	}
	return val * f;
}
int32_t main(){
	n = rit();
	REP(i , 1 , n + 1) x[i] = rit() , y[i] = rit() , r[i] = rit();
	// REP(i , 1 , n + 1) cin >> x[i] >> y[i] >> r[i];

	REP(i , 1 , n + 1) sol[i] = i;
	sort(sol + 1 , sol + 1 + n , cmp);
	// REP(idx , 1 , n + 1){ int i = sol[idx];
	// 	if(ans[i]) continue;
	// 	REP(j , 1 , n + 1) if(ans[j] == 0 && tch(i , j)) ans[j] = i;
	// }
	REP(i , 1 , n + 1) las.pb(i);
	int del = 1000000;
	REP(idx , 1 , n + 1){ int i = sol[idx];
		if(ans[i]) continue;
		// DBGG("solve = " , i);
		if(R / 5 > r[i] && del > 1000){
			del = 0;
			cc.clear();
			R = r[sol[1]];
			vector<int> nw;
			for(auto j : las){
				if(ans[j]) continue;
				nw.pb(j);
				int xx = x[j] / R , yy = y[j] / R;
				if(cc.find(trs(xx , yy)) == cc.end()){
					v[pos].clear();
					v[pos].pb(0 , 1);
					cc[trs(xx , yy)] = pos ++;
					if(pos == MAX) pos = 0;
				}
				v[cc[trs(xx , yy)]].pb(j , v[cc[trs(xx , yy)]].size() + 1);
			}
			swap(nw , las);
		}
		int xx = x[i] / R , yy = y[i] / R;
		REP(ii , xx - 2 , xx + 3) REP(jj , yy - 2 , yy + 3){
			if(cc.find(trs(ii , jj)) != cc.end()){
				int id = cc[trs(ii , jj)] , pre = 0;
				while(v[id][pre].B < v[id].size()){
					int now = v[id][pre].B;
					if(tch(i , v[id][now].A)){
						ans[v[id][now].A] = i;
						del ++;
						v[id][pre].B = v[id][now].B;
					}
					else pre = now;
				}
				// for(auto to : v[id]){
				// 	if(ans[to.A] == 0 && tch(i , to.A)) ans[to.A] = i;
				// }
			}
		}
	}
	REP(i , 1 , n + 1) printf("%d " , ans[i]);
	puts("");
    return 0;
}

// 7 2 7 4 5 6 7 7 4 7 6

Compilation message (stderr)

circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:102:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(v[id][pre].B < v[id].size()){

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