답안 #95395 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95395	2019-01-31T11:59:14 Z	pranjalssh	원 고르기 (APIO18_circle_selection)	C++11	45 / 100	1346 ms	54776 KB

circle_selection

/*
	Simulate process by checking all circles in square of width 4*r. Use a kd-tree for this.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


const int N = 3e5 + 10;
vi x, y, r;
struct node {
	int l, r, sum, mid;
	int aid;
	node(): l(0), r(0), sum(0), mid(0), aid(0) {}
};
vector<node> T;
vector<vector<int>> A;
vi xc, yc;
vi par;
inline bool intersect(int i, int j) {
	return (x[i] - x[j]) * 1LL * (x[i] - x[j]) + (y[i] - y[j]) * 1LL * (y[i] - y[j]) <= (r[i] + r[j]) * 1LL * (r[i] + r[j]);
}

inline int make_node() {
	T.emplace_back();
	return sz(T) - 1;
}

int build(int no, bool dim, int xl, int xr, int yl, int yr, const vi& ids) {
	if (ids.empty()) return no;
	if (no == 0) no = make_node();
	bool g = 1;
	FOR (i, 1, sz(ids) - 1) if (x[ids[i]] != x[ids[0]] or y[ids[i]] != y[ids[0]]) {g = 0; break;}
	if (g) {
		T[no].sum = sz(ids);
		A.emplace_back(ids);
		T[no].aid = sz(A)-1;
		return no;
	}
	if (dim) {
		int mid = rand() % (yr-yl) + yl;
		vi lids, rids;
		for (int it : ids) {
			if (y[it] <= yc[mid]) lids.emplace_back(it);
			else rids.emplace_back(it);
		}
		int L = build(0, 0, xl, xr, yl, mid, lids);
		int R = build(0, 0, xl, xr, mid + 1, yr, rids);
		T[no].l = L, T[no].r = R;
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
		T[no].mid = mid;
	} else {
		int mid = rand() % (xr-xl) + xl;
		vi lids, rids;
		for (int it : ids) {
			if (x[it] <= xc[mid]) lids.emplace_back(it);
			else rids.emplace_back(it);
		}
		int L = build(0, 1, xl, mid, yl, yr, lids);
		int R = build(0, 1, mid + 1, xr, yl, yr, rids);
		T[no].l = L, T[no].r = R;
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
		T[no].mid = mid;
	}
	return no;
}

int xu, xv, yu, yv, bc;
vi rem;

void get(int no, bool dim, int xl, int xr, int yl, int yr) {
	if (T[no].sum == 0) return;

	if (xr < xu or xl > xv) return;
	if (yr < yu or yl > yv) return;

	if (T[no].l == 0 and T[no].r == 0) {
		for (int it: A[T[no].aid]) if (intersect(it, bc)) {
			par[it] = bc;
			rem.emplace_back(it);
			T[no].sum--;
		}

		reverse(all(rem));
		vi& a = A[T[no].aid];
		int j = 0;
		FOR (i, 0, sz(a) - 1) {
			if (rem.empty() or a[i] != rem.back()) {
				a[j] = a[i];
				++j;
			} else {
				rem.pop_back();
			}
		}
		a.resize(j);
		rem.clear();
		return;
	}

	if (dim) {
		int mid = T[no].mid;
		get(T[no].l, 0, xl,xr,yl, mid);
		get(T[no].r, 0, xl, xr, mid+1, yr);
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
	} else {
		int mid = T[no].mid;
		get(T[no].l, 1, xl, mid, yl, yr);
		get(T[no].r, 1, mid+1, xr, yl, yr);
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
	}

}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n;
	x.resize(n), y.resize(n), r.resize(n);
	par = vi(n, -1);

	FOR (i, 0, n - 1) {
		cin >> x[i] >> y[i] >> r[i];
		xc.emplace_back(x[i]);
		yc.emplace_back(y[i]);
	}
	xc.emplace_back(-inf), xc.emplace_back(inf);
	yc.emplace_back(-inf), yc.emplace_back(inf);
	sort(all(xc)); xc.erase(unique(all(xc)), xc.end());
	sort(all(yc)); yc.erase(unique(all(yc)), yc.end());

	vi id(n); iota(all(id), 0);
	sort(all(id), [&](int x, int y) {
		if (r[x] == r[y]) return x < y;
		return r[x] > r[y];
	});

	T.reserve(2e7);

	T.emplace_back();
	int root = build(0, 0, 0, sz(xc)-1, 0, sz(yc)-1, id);

	for (int i : id) if (par[i] == -1) {
			bc = i;
			xu = max(x[i] - 2LL * r[i], (ll) - inf);
			xu = lower_bound(all(xc), xu) - xc.begin();
			xv = min(x[i] + 2LL * r[i], (ll)inf);
			xv = upper_bound(all(xc), xv) - xc.begin()-1;

			yu = max(y[i] - 2LL * r[i], (ll) - 1e9);
			yu = lower_bound(all(yc), yu) - yc.begin();
			yv = min(y[i] + 2LL * r[i], (ll)1e9);
			yv = upper_bound(all(yc), yv) - yc.begin()-1;

			get(root, 0, 0, sz(xc)-1, 0, sz(yc)-1);
		}

	FOR (i, 0, n - 1) cout << par[i] + 1 << " ";



	return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	3 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct
19	Correct	9 ms	1400 KB	Output is correct
20	Correct	9 ms	1372 KB	Output is correct
21	Correct	10 ms	1400 KB	Output is correct
22	Correct	13 ms	1404 KB	Output is correct
23	Correct	13 ms	1400 KB	Output is correct
24	Correct	12 ms	1404 KB	Output is correct
25	Correct	12 ms	1360 KB	Output is correct
26	Correct	13 ms	1400 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	204 ms	27224 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	376 ms	16656 KB	Output is correct
3	Correct	1225 ms	49528 KB	Output is correct
4	Correct	1179 ms	48192 KB	Output is correct
5	Correct	1204 ms	54560 KB	Output is correct
6	Correct	529 ms	33464 KB	Output is correct
7	Correct	270 ms	18660 KB	Output is correct
8	Correct	45 ms	4916 KB	Output is correct
9	Correct	1346 ms	52320 KB	Output is correct
10	Correct	1254 ms	54776 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1189 ms	48084 KB	Output is correct
2	Correct	1055 ms	48620 KB	Output is correct
3	Correct	672 ms	47904 KB	Output is correct
4	Correct	1142 ms	48608 KB	Output is correct
5	Correct	1054 ms	48996 KB	Output is correct
6	Correct	565 ms	48820 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	3 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct
19	Correct	9 ms	1400 KB	Output is correct
20	Correct	9 ms	1372 KB	Output is correct
21	Correct	10 ms	1400 KB	Output is correct
22	Correct	13 ms	1404 KB	Output is correct
23	Correct	13 ms	1400 KB	Output is correct
24	Correct	12 ms	1404 KB	Output is correct
25	Correct	12 ms	1360 KB	Output is correct
26	Correct	13 ms	1400 KB	Output is correct
27	Correct	17 ms	2212 KB	Output is correct
28	Correct	16 ms	2228 KB	Output is correct
29	Correct	14 ms	2228 KB	Output is correct
30	Correct	29 ms	2236 KB	Output is correct
31	Correct	24 ms	2296 KB	Output is correct
32	Correct	25 ms	2168 KB	Output is correct
33	Correct	166 ms	16844 KB	Output is correct
34	Correct	183 ms	16664 KB	Output is correct
35	Correct	206 ms	16504 KB	Output is correct
36	Correct	368 ms	16332 KB	Output is correct
37	Correct	370 ms	16584 KB	Output is correct
38	Correct	380 ms	16612 KB	Output is correct
39	Runtime error	64 ms	10092 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	3 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct
19	Correct	9 ms	1400 KB	Output is correct
20	Correct	9 ms	1372 KB	Output is correct
21	Correct	10 ms	1400 KB	Output is correct
22	Correct	13 ms	1404 KB	Output is correct
23	Correct	13 ms	1400 KB	Output is correct
24	Correct	12 ms	1404 KB	Output is correct
25	Correct	12 ms	1360 KB	Output is correct
26	Correct	13 ms	1400 KB	Output is correct
27	Runtime error	204 ms	27224 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

답안 #95395

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0