Submission #169766

#	Time	Username	Problem	Language	Result	Execution time	Memory
169766		ZwariowanyMarcin	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3113 ms	419988 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);
}

map <pair<int, int>, vector <int> > mapa;

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

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

vector <int> wywal;

void solve(int x, int y, int id) {
	for(int i = 0; i < ss(mapa[mp(x, y)]); ++i) {
		auto it = mapa[mp(x, y)][i];
		if(ans[it]) continue;
		if(inter(t[id], t[it])) {
			ans[it] = id;
			wywal.pb(i);
		}
	}
	for(int i = ss(wywal) - 1; 0 <= i; --i) {
		int it = wywal[i];
		swap(mapa[mp(x, y)][it], mapa[mp(x, y)].back());
		mapa[mp(x, y)].pop_back();
	}
	wywal.clear();
}
		
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 += INF;
		t[i].y += INF;
		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;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circle_selection.cpp:61: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: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13