oj.uz

Submission #415068

# Submission time Handle Problem Language Result Execution time Memory
415068 2021-05-31T13:38:54 Z hhhhaura Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 85424 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 100
#define MOD 1000000007
#define eps (1e-9)

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

using namespace std;

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
namespace solver {
	int n, r, c, w, ii;
	vector<unordered_set<int>> v;
	vector<pii> a;
	vector<int> vis, ord, rad;
	unordered_map<int, int> mp;
	void init_(int _n) {
		n = _n;
		a.assign(n + 1, {0, 0});
		rad.assign(n + 1, 0);
		vis.assign(n + 1, 0);
		ord.clear();
		mp.clear();
		rep(i, 1, n) ord.push_back(i);
	}
	bool cmp(int a, int b) {
		if(rad[a] != rad[b]) 
			return rad[a] > rad[b];
		else return a < b;
	}
	int get_id(pii a) {
		int xx = (a.x + INF)/ w;
		int yy = (a.y + INF)/ w;
		return xx * c + yy;
	}
	void reconstruct(int x) {
		w = x, ii = 0;
		r = ceil(2 * INF, w);
		c = ceil(2 * INF, w);
		v.assign(n + 1, unordered_set<int>());
		mp.clear();
		rep(i, 1, n) if(!vis[i]) {
			pii cur = a[i]; int id = get_id(cur);
			if(mp.find(id) == mp.end()) {
				mp[id] = ++ii;
			}
			v[mp[id]].insert(i);
		}
	}
	int dis2(pii a, pii b) {
		return (a.x - b.x) * (a.x - b.x) + 
			(a.y - b.y) * (a.y - b.y); 
	}
	void operate(int id, int x) {
		rep(xx, -2, 2) rep(yy, -2, 2) {
			int i = xx * c + id + yy;
			if(mp.find(i) == mp.end()) continue;
			int bk = mp[i];
			auto it = v[bk].begin();
			while(it != v[bk].end()) {
				if(dis2(a[*it], a[x]) <= 
					(rad[*it] + rad[x]) * (rad[*it] + rad[x])) {
					vis[*it] = x; 
					auto cur = it;  it = next(cur);
					v[bk].erase(cur);
				}
				else it = next(it);
			}	
		}
		return;
	}
	void solve() {
		sort(all(ord), cmp);
		reconstruct(rad[ord[0]]);
		for(auto i : ord) if(!vis[i]) { 
			if(rad[i] * 2 <= w) reconstruct(rad[i]);
			int id = get_id(a[i]); operate(id, i);
		}
		rep(i, 1, n) cout << vis[i] << " \n"[i == n]; 
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n; cin >> n;
	init_(n);
	rep(i, 1, n) {
		cin >> a[i].x >> a[i].y;
		cin >> rad[i];
	}
	solve();
	return 0;
}

Compilation message

circle_selection.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
circle_selection.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
circle_selection.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 308 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 5 ms 1100 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 5 ms 1100 KB Output is correct
22 Correct 11 ms 1800 KB Output is correct
23 Correct 11 ms 1740 KB Output is correct
24 Correct 14 ms 1780 KB Output is correct
25 Correct 12 ms 1740 KB Output is correct
26 Correct 11 ms 1716 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 43328 KB Output is correct
2 Correct 406 ms 44720 KB Output is correct
3 Correct 358 ms 47056 KB Output is correct
4 Correct 250 ms 43316 KB Output is correct
5 Correct 569 ms 46108 KB Output is correct
6 Correct 1024 ms 64692 KB Output is correct
7 Correct 510 ms 47088 KB Output is correct
8 Correct 530 ms 49288 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 898 ms 18164 KB Output is correct
3 Execution timed out 3036 ms 47644 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2029 ms 63932 KB Output is correct
2 Correct 1742 ms 85424 KB Output is correct
3 Execution timed out 3017 ms 49804 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 308 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 5 ms 1100 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 5 ms 1100 KB Output is correct
22 Correct 11 ms 1800 KB Output is correct
23 Correct 11 ms 1740 KB Output is correct
24 Correct 14 ms 1780 KB Output is correct
25 Correct 12 ms 1740 KB Output is correct
26 Correct 11 ms 1716 KB Output is correct
27 Correct 11 ms 1932 KB Output is correct
28 Correct 10 ms 2048 KB Output is correct
29 Correct 10 ms 1920 KB Output is correct
30 Correct 28 ms 3232 KB Output is correct
31 Correct 22 ms 2900 KB Output is correct
32 Correct 26 ms 3168 KB Output is correct
33 Correct 91 ms 15040 KB Output is correct
34 Correct 90 ms 14784 KB Output is correct
35 Correct 138 ms 15008 KB Output is correct
36 Correct 468 ms 21184 KB Output is correct
37 Correct 427 ms 23084 KB Output is correct
38 Correct 648 ms 19072 KB Output is correct
39 Correct 697 ms 24092 KB Output is correct
40 Correct 685 ms 24072 KB Output is correct
41 Correct 558 ms 24064 KB Output is correct
42 Correct 808 ms 15264 KB Output is correct
43 Correct 254 ms 29096 KB Output is correct
44 Correct 296 ms 29192 KB Output is correct
45 Correct 246 ms 29120 KB Output is correct
46 Correct 243 ms 29100 KB Output is correct
47 Correct 265 ms 29084 KB Output is correct
48 Correct 347 ms 29164 KB Output is correct
49 Correct 309 ms 29084 KB Output is correct
50 Correct 308 ms 29176 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 308 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 5 ms 1100 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 5 ms 1100 KB Output is correct
22 Correct 11 ms 1800 KB Output is correct
23 Correct 11 ms 1740 KB Output is correct
24 Correct 14 ms 1780 KB Output is correct
25 Correct 12 ms 1740 KB Output is correct
26 Correct 11 ms 1716 KB Output is correct
27 Correct 255 ms 43328 KB Output is correct
28 Correct 406 ms 44720 KB Output is correct
29 Correct 358 ms 47056 KB Output is correct
30 Correct 250 ms 43316 KB Output is correct
31 Correct 569 ms 46108 KB Output is correct
32 Correct 1024 ms 64692 KB Output is correct
33 Correct 510 ms 47088 KB Output is correct
34 Correct 530 ms 49288 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 898 ms 18164 KB Output is correct
37 Execution timed out 3036 ms 47644 KB Time limit exceeded
38 Halted 0 ms 0 KB -