Submission #169771

#	Time	Username	Problem	Language	Result	Execution time	Memory
169771		ZwariowanyMarcin	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1120 ms	22424 KiB

circle_selection

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int INF = 2e9;

struct circle {
	int x, y, r;
};

bool inter(circle &a, circle &b) {
	return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y) <= 1ll * (a.r + b.r) * (a.r + b.r);
}

struct gao {
	int X, Y, ID;
	gao(int X, int Y, int ID) : X(X), Y(Y), ID(ID) {}
	bool operator < (gao a) {
		return mp(X, Y) < mp(a.X, a.Y);
	} 
};
vector <gao> V;

int n;
circle t[300005];
int cur = INF;
vector <int> v;
int ans[300005];

void go() {
	V.clear();
	for(int i = 1; i <= n; ++i) {
		if(ans[i]) continue;
		V.pb({t[i].x / cur, t[i].y / cur, i});
	}
	sort(V.begin(), V.end());
}

vector <int> wywal;

inline void solve(const int &x, const int &y, const int &id) {
	auto it = lower_bound(V.begin(), V.end(), gao(x, y, -1));
	while(it != V.end() && it->X == x && it->Y == y) {
		if(ans[it->ID]) {
			it++;
			continue;
		}
		//cat(id);
		//cat(it->ID);
		if(inter(t[id], t[it->ID]))
			ans[it->ID] = id;
		it++;
	}	
}
		
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d %d %d", &t[i].x, &t[i].y, &t[i].r);
		t[i].x += 1000000000;
		t[i].y += 1000000000;
		v.pb(i);
	}
	
	sort(v.begin(), v.end(), [](int a, int b) {
		if(t[a].r != t[b].r)
			return t[a].r < t[b].r;
		return a > b;
	});
	
	go();
	for(int i = n - 1; 0 <= i; --i) {
		int ja = v[i];
		if(!ans[ja]) {
			if(2 * t[ja].r < cur) {
				cur = t[ja].r;
				go();
			}
			for(int x = t[ja].x / cur - 2; x <= t[ja].x / cur + 2; ++x)
				for(int y = t[ja].y / cur - 2; y <= t[ja].y / cur + 2; ++y)
					solve(x, y, ja);
		}
	}
				
	for(int i = 1; i <= n; ++i)
		printf("%d ", ans[i]);
	
	return 0;
}
/* 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:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circle_selection.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t[i].x, &t[i].y, &t[i].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