Submission #334385

#	Time	Username	Problem	Language	Result	Execution time	Memory
334385		Seanliu	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1432 ms	49664 KiB

circle_selection

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <unordered_map>
#include <numeric>
#include <algorithm>
#include <vector>
#define int long long int
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int maxN = 3e5 + 326, maxC = 1e9 + 326;
int ans[maxN], x[maxN], y[maxN], r[maxN], N, ord[maxN], curSz;

unordered_map<int, vector<int> > mp;

inline char readchar(){
	const int S = 1<<16;
	static char buf[S], *p = buf, *q = buf;
	return p == q and (q = (p = buf) + fread(buf, 1, S, stdin)) == buf ? EOF : *p++;
}

inline void Read(int &a){
	static char c;
	while(((c = readchar()) < '0' or c > '9') and c != '-' and c != EOF);
	if(c == '-'){
		a = 0;
		while((c = readchar()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
	} else {
		a = c ^ '0';
		while((c = readchar()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
	}
}

char outbuf[1 << 16]; int outp;
inline void W(int n){
	static char buf[12], p;
	if(n == 0) outbuf[outp++] = '0';
	p = 0;
	if(n < 0){
		outbuf[outp++] = '-';
		while(n) buf[p++] = '0' - (n % 10), n /= 10;
	} else {
		while(n) buf[p++] = '0' + (n % 10), n /= 10;
	}
	for(--p; p >= 0; --p) outbuf[outp++] = buf[p];
	outbuf[outp++] = ' ';
	if(outp > (1 << 16)-12) fwrite(outbuf, 1, outp, stdout), outp = 0;
}

inline void assign(){
	mp = unordered_map<int, vector<int> >();
	for(int i = 1; i <= N; i++){
		if(ans[i]) continue;
		int k = maxC * (x[i] / curSz) + (y[i] / curSz);
		if(!mp.count(k)) mp[k] = vector<int>();
		mp[k].push_back(i);
	}
}

inline bool intersect(int i, int j){
	return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= r[i] * r[i] + 2 * r[i] * r[j] + r[j] * r[j];
}

inline void kill(int sel){
	int X = x[sel] / curSz, Y = y[sel] / curSz;
	for(int i = (X - 2) * maxC; i <= (X + 2) * maxC; i += maxC){
		for(int j = Y - 2; j <= Y + 2; j++){
			if(!mp.count(i + j)) continue;
			for(int ind : mp[i + j]){
				if(ans[ind]) continue;
				if(intersect(ind, sel)){
					ans[ind] = sel;
				}
			}
		}
	}
}

signed main(){
	Read(N);
	mp.reserve(N);
	for(int i = 1; i <= N; i++){
		Read(x[i]);
		Read(y[i]);
		Read(r[i]);
	}
	iota(ord, ord + N + 1, 0);
	sort(ord + 1, ord + N + 1, [](int a, int b){
		return (r[a] == r[b] ? a < b : r[a] > r[b]);
	});
	curSz = 1LL << 32;
	for(int i = 1; i <= N; i++){
		if(ans[ord[i]]) continue;
		bool f = true;
		while(curSz >= 2 * r[ord[i]]){
			curSz /= 2;	
			f = false;
		}
		if(!f) assign();
		kill(ord[i]);
	}
	for(int i = 1; i <= N; i++) W(ans[i]);
	fwrite(outbuf, 1, outp, stdout);
	puts("");
}

Compilation message (stderr)

circle_selection.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("Ofast")
      | 
circle_selection.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
circle_selection.cpp: In function 'void W(long long int)':
circle_selection.cpp:42:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |   while(n) buf[p++] = '0' - (n % 10), n /= 10;
      |                ~^~
circle_selection.cpp:44:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |   while(n) buf[p++] = '0' + (n % 10), n /= 10;
      |                ~^~
circle_selection.cpp:46:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |  for(--p; p >= 0; --p) outbuf[outp++] = buf[p];
      |                                             ^

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