Submission #48859

#	Time	Username	Problem	Language	Result	Execution time	Memory
48859		kriii	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2757 ms	658428 KiB

circle_selection

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int N,X[300300],Y[300300],R[300300];
int C,XP[600600],p[300300][2];
pair<int, int> CR[300300];
int pick[300300];

const int Z = 1 << 21;
vector<pair<int, int> > grp[Z*2];
vector<int> par[Z*2];

bool intersect(int i, int j)
{
	return (long long)(X[i] - X[j]) * (X[i] - X[j]) + (long long)(Y[i] - Y[j]) * (Y[i] - Y[j])
		<= + (long long)(R[i] + R[j]) * (R[i] + R[j]);
}

int find(vector<int> &par, int x)
{
	if (par[x] != x) par[x] = find(par,par[x]);
	return par[x];
}

void go(int x, int i)
{
	auto &G = grp[x];
	auto &P = par[x];
	int j = lower_bound(G.begin(),G.end(),make_pair(Y[i]-R[i],0)) - G.begin();
	int u = Y[i] + R[i];
	while (j < G.size() && G[j].first <= u){
		if (find(P,j) != j){
			j = find(P,j);
			continue;
		}
		if (pick[G[j].second] == 0 && intersect(i,G[j].second)) pick[G[j].second] = i;
		if (pick[G[j].second]) P[j] = j + 1;
		else j++;
	}
}

int main()
{
	scanf ("%d",&N);
	for (int i=1;i<=N;i++){
		scanf ("%d %d %d",&X[i],&Y[i],&R[i]);
		XP[C++] = X[i] - R[i];
		XP[C++] = X[i] + R[i];
		CR[i-1] = {R[i],-i};
	}

	sort(XP,XP+C);
	C = unique(XP,XP+C) - XP;
	for (int i=1;i<=N;i++){
		p[i][0] = lower_bound(XP,XP+C,X[i]-R[i]) - XP + Z;
		p[i][1] = lower_bound(XP,XP+C,X[i]+R[i]) - XP + Z;
		grp[p[i][0]].push_back({Y[i]-R[i],i});
		grp[p[i][0]].push_back({Y[i]+R[i],i});
		grp[p[i][1]].push_back({Y[i]-R[i],i});
		grp[p[i][1]].push_back({Y[i]+R[i],i});
	}

	for (int i=Z;i<Z*2;i++) if (!grp[i].empty()) sort(grp[i].begin(),grp[i].end());
	for (int i=Z-1;i>=1;i--){
		auto &u = grp[i*2], &v = grp[i*2+1], &w = grp[i];
		w.resize(u.size()+v.size());
		int p = 0, q = 0, r = 0;
		while (p < u.size() || q < v.size()){
			w[r++] = (q == v.size() || (p < u.size() && u[p] < v[q])) ? u[p++] : v[q++];
		}
	}
	for (int i=1;i<Z*2;i++){
		par[i].resize(grp[i].size()+1);
		for (int j=0;j<par[i].size();j++) par[i][j] = j;
	}

	sort(CR,CR+N);
	reverse(CR,CR+N);

	for (int j=0;j<N;j++) if (pick[-CR[j].second] == 0){
		int i = -CR[j].second;
		int x = p[i][0];
		int y = p[i][1];
		while (x < y){
			if (x & 1) go(x++,i);
			if (~y & 1) go(y--,i);
			x /= 2; y /= 2;
		} if (x == y) go(x,i);
	}

	for (int i=1;i<=N;i++) printf ("%d%c",pick[i],i<N?' ':'\n');

	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'void go(int, int)':
circle_selection.cpp:33:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < G.size() && G[j].first <= u){
         ~~^~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p < u.size() || q < v.size()){
          ~~^~~~~~~~~~
circle_selection.cpp:70:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p < u.size() || q < v.size()){
                          ~~^~~~~~~~~~
circle_selection.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    w[r++] = (q == v.size() || (p < u.size() && u[p] < v[q])) ? u[p++] : v[q++];
              ~~^~~~~~~~~~~
circle_selection.cpp:71:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    w[r++] = (q == v.size() || (p < u.size() && u[p] < v[q])) ? u[p++] : v[q++];
                                ~~^~~~~~~~~~
circle_selection.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<par[i].size();j++) par[i][j] = j;
                ~^~~~~~~~~~~~~~
circle_selection.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&N);
  ~~~~~~^~~~~~~~~
circle_selection.cpp:48:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&X[i],&Y[i],&R[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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