oj.uz

Submission #262989

# Submission time Handle Problem Language Result Execution time Memory
262989 2020-08-13T11:42:34 Z _7_7_ Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 43868 KB 
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;
typedef long long ll;
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 3e5 + 12;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;
 

struct point {
	int x, y, r, id;
	bool operator < (const point &a) const {
		if (r != a.r)
			return r > a.r;
		return id < a.id;
	}
} a[N];

int n, res[N], bl;
set < pii > q;
vpii vals;
pii b[N];
vi m[N];

inline int getId (pii x) {
	return lower_bound(all(vals), x) - vals.begin();
}

inline bool check (int i, int j) {
	return (a[i].x - a[j].x) * 1ll * (a[i].x - a[j].x) + (a[i].y - a[j].y) * 1ll * (a[i].y - a[j].y) <= (a[i].r + a[j].r) * 1ll * (a[i].r + a[j].r);
}


inline void build () {
	vals.clear();
	q.clear();
	for (int i = 1; i <= n; ++i)
		if (!res[a[i].id]) {
			b[i] = mp(a[i].x / bl, a[i].y / bl);
			vals.pb(b[i]);
			q.insert(b[i]);
		}

	sort(all(vals));
	vals.resize(unique(all(vals)) - vals.begin());

	for (int i = 0; i < sz(vals); ++i)
		m[i].clear();

	for (int i = 1; i <= n; ++i)
		if (!res[a[i].id])
			m[getId(b[i])].pb(i);
}

main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
		a[i].id = i;
	}

	sort(a + 1, a + 1 + n);
	        	
	bl = a[1].r;
	build();

	for (int i = 1; i <= n; ++i) 
		if (!res[a[i].id]) {
			if (a[i].r + a[i].r <= bl) {
				bl = a[i].r;
				build();
			}

			vector < point > V;
			point Mn;
			Mn.r = -inf;

			for (int c = -2; c <= 2; ++c)
				for (int d = -2; d <= 2; ++d) {
				    pii cur = mp(b[i].f + c, b[i].s + d);
					if (!q.count(cur)) 
						continue;

					int z = getId(cur);	

					for (auto j : m[z])
						if (!res[a[j].id] && check(i, j)) {
							if (a[j] < Mn) 
								Mn = a[j];
							V.pb(a[j]);
						}
				}

			if (Mn < a[i]) {
				res[a[i].id] = Mn.id; 
			    continue;
			}

			res[a[i].id] = a[i].id;
			for (auto j : V)
				res[j.id] = a[i].id;
		}
	
	for (int i = 1; i <= n; ++i)
		printf("%d ", res[i]);
}

Compilation message

circle_selection.cpp:90:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main () {
      |       ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:130:18: warning: 'Mn.point::id' may be used uninitialized in this function [-Wmaybe-uninitialized]
  130 |     res[a[i].id] = Mn.id;
      |     ~~~~~~~~~~~~~^~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 6 ms 7432 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 7 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7424 KB Output is correct
14 Correct 5 ms 7400 KB Output is correct
15 Correct 5 ms 7424 KB Output is correct
16 Correct 6 ms 7424 KB Output is correct
17 Correct 10 ms 7424 KB Output is correct
18 Correct 15 ms 7504 KB Output is correct
19 Correct 9 ms 7896 KB Output is correct
20 Correct 10 ms 7936 KB Output is correct
21 Correct 10 ms 7808 KB Output is correct
22 Correct 22 ms 8064 KB Output is correct
23 Correct 51 ms 8064 KB Output is correct
24 Correct 22 ms 8064 KB Output is correct
25 Correct 20 ms 8064 KB Output is correct
26 Correct 20 ms 8064 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 30648 KB Output is correct
2 Correct 285 ms 28456 KB Output is correct
3 Correct 238 ms 27988 KB Output is correct
4 Correct 281 ms 31624 KB Output is correct
5 Correct 392 ms 22416 KB Output is correct
6 Correct 1057 ms 31828 KB Output is correct
7 Correct 449 ms 23412 KB Output is correct
8 Correct 548 ms 24916 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 611 ms 19696 KB Output is correct
3 Correct 2488 ms 43816 KB Output is correct
4 Correct 2452 ms 43840 KB Output is correct
5 Correct 2630 ms 39188 KB Output is correct
6 Correct 875 ms 23268 KB Output is correct
7 Correct 341 ms 16104 KB Output is correct
8 Correct 58 ms 9332 KB Output is correct
9 Execution timed out 3064 ms 41168 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2023 ms 43868 KB Output is correct
2 Correct 1523 ms 43740 KB Output is correct
3 Correct 723 ms 27356 KB Output is correct
4 Correct 1457 ms 43868 KB Output is correct
5 Correct 1488 ms 43868 KB Output is correct
6 Correct 424 ms 22748 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 6 ms 7432 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 7 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7424 KB Output is correct
14 Correct 5 ms 7400 KB Output is correct
15 Correct 5 ms 7424 KB Output is correct
16 Correct 6 ms 7424 KB Output is correct
17 Correct 10 ms 7424 KB Output is correct
18 Correct 15 ms 7504 KB Output is correct
19 Correct 9 ms 7896 KB Output is correct
20 Correct 10 ms 7936 KB Output is correct
21 Correct 10 ms 7808 KB Output is correct
22 Correct 22 ms 8064 KB Output is correct
23 Correct 51 ms 8064 KB Output is correct
24 Correct 22 ms 8064 KB Output is correct
25 Correct 20 ms 8064 KB Output is correct
26 Correct 20 ms 8064 KB Output is correct
27 Correct 16 ms 8336 KB Output is correct
28 Correct 16 ms 8320 KB Output is correct
29 Correct 14 ms 8312 KB Output is correct
30 Correct 52 ms 8720 KB Output is correct
31 Correct 41 ms 8704 KB Output is correct
32 Correct 39 ms 8696 KB Output is correct
33 Correct 94 ms 14316 KB Output is correct
34 Correct 92 ms 14316 KB Output is correct
35 Correct 100 ms 14316 KB Output is correct
36 Correct 503 ms 19496 KB Output is correct
37 Correct 553 ms 19564 KB Output is correct
38 Correct 522 ms 19560 KB Output is correct
39 Correct 510 ms 19428 KB Output is correct
40 Correct 545 ms 19628 KB Output is correct
41 Correct 541 ms 19560 KB Output is correct
42 Correct 464 ms 19488 KB Output is correct
43 Correct 371 ms 19324 KB Output is correct
44 Correct 387 ms 19308 KB Output is correct
45 Correct 382 ms 19304 KB Output is correct
46 Correct 400 ms 19228 KB Output is correct
47 Correct 454 ms 19176 KB Output is correct
48 Correct 453 ms 19432 KB Output is correct
49 Correct 448 ms 19440 KB Output is correct
50 Correct 400 ms 19488 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 6 ms 7432 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 7 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7424 KB Output is correct
14 Correct 5 ms 7400 KB Output is correct
15 Correct 5 ms 7424 KB Output is correct
16 Correct 6 ms 7424 KB Output is correct
17 Correct 10 ms 7424 KB Output is correct
18 Correct 15 ms 7504 KB Output is correct
19 Correct 9 ms 7896 KB Output is correct
20 Correct 10 ms 7936 KB Output is correct
21 Correct 10 ms 7808 KB Output is correct
22 Correct 22 ms 8064 KB Output is correct
23 Correct 51 ms 8064 KB Output is correct
24 Correct 22 ms 8064 KB Output is correct
25 Correct 20 ms 8064 KB Output is correct
26 Correct 20 ms 8064 KB Output is correct
27 Correct 253 ms 30648 KB Output is correct
28 Correct 285 ms 28456 KB Output is correct
29 Correct 238 ms 27988 KB Output is correct
30 Correct 281 ms 31624 KB Output is correct
31 Correct 392 ms 22416 KB Output is correct
32 Correct 1057 ms 31828 KB Output is correct
33 Correct 449 ms 23412 KB Output is correct
34 Correct 548 ms 24916 KB Output is correct
35 Correct 5 ms 7424 KB Output is correct
36 Correct 611 ms 19696 KB Output is correct
37 Correct 2488 ms 43816 KB Output is correct
38 Correct 2452 ms 43840 KB Output is correct
39 Correct 2630 ms 39188 KB Output is correct
40 Correct 875 ms 23268 KB Output is correct
41 Correct 341 ms 16104 KB Output is correct
42 Correct 58 ms 9332 KB Output is correct
43 Execution timed out 3064 ms 41168 KB Time limit exceeded
44 Halted 0 ms 0 KB -