oj.uz

Submission #1071009

# Submission time Handle Problem Language Result Execution time Memory
1071009 2024-08-22T23:25:50 Z pawned Circle selection (APIO18_circle_selection) C++17
49 / 100
 3000 ms 73008 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

bool intersect(int x1, int y1, int x2, int y2, int r1, int r2) {
	ll dx = abs(x1 - x2);
	ll dy = abs(y1 - y2);
	ll dt = r1 + r2;
	if (dt * dt >= dx * dx + dy * dy)
		return true;
	return false;
}

int main() {
	fastIO();
	int N;
	cin>>N;
	vector<pair<ii, int>> cr(N);
	// {{x, y}, r}
	set<pair<ii, ii>> all;
	// {{r, -id}, {x, y}}
	map<int, set<pair<int, ii>>> allx;	// maps x coord to all {y, {r, id}}
	for (int i = 0; i < N; i++) {
		int x, y, r;
		cin>>x>>y>>r;
		all.insert({{r, -i}, {x, y}});
		allx[x].insert({y, {r, i}});
	}
	vi par(N, -1);
	int rem = N;
	while (rem > 0) {
		auto it = --all.end();
		int r = (*it).fi.fi;
		int id = -(*it).fi.se;
		int x = (*it).se.fi;
		int y = (*it).se.se;
//		cout<<"at "<<id<<endl;
		// consider all from x in x-2r to x+2r, y in y-2r to r+2r
		int xl = max((ll)(x) - 2 * (ll)(r), (ll)(-2e9));
		int xh = min((ll)(x) + 2 * (ll)(r), (ll)(2e9));
		auto it2 = allx.lower_bound(xl);
		while (it2 != allx.end() && (*it2).fi <= xh) {
			// do another search inside
			int cx = (*it2).fi;
			vector<pair<ll, ii>> toremove;
			int dx = abs(xh - cx);
			// can do up to sqrt for yh
			ll dy = 2e9;
			int yl = max((ll)(y) - dy, (ll)(-2e9));
			int yh = min((ll)(y) + dy, (ll)(2e9));
			auto it3 = allx[cx].lower_bound({yl, {-1, -1}});
			while (it3 != allx[cx].end() && (*it3).fi <= yh) {
				int cy = (*it3).fi;
				int cr = (*it3).se.fi;
				int cid = (*it3).se.se;
				if (intersect(x, y, cx, cy, r, cr)) {
					toremove.pb(*it3);
				}
				it3++;
			}
			for (pair<int, ii> p : toremove) {
				par[p.se.se] = id;
//				cout<<"erased "<<p.se.se<<endl;
				allx[cx].erase(p);
				all.erase({{p.se.fi, -p.se.se}, {cx, p.fi}});
				rem--;
			}
			it2++;
		}
	}
//	cout<<"ANSWER: ";
	for (int x : par)
		cout<<(x + 1)<<" ";
	cout<<endl;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:70:9: warning: unused variable 'cid' [-Wunused-variable]
   70 |     int cid = (*it3).se.se;
      |         ^~~
circle_selection.cpp:61:8: warning: unused variable 'dx' [-Wunused-variable]
   61 |    int dx = abs(xh - cx);
      |        ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 5 ms 1624 KB Output is correct
20 Correct 5 ms 1628 KB Output is correct
21 Correct 7 ms 1628 KB Output is correct
22 Correct 8 ms 1628 KB Output is correct
23 Correct 37 ms 1620 KB Output is correct
24 Correct 8 ms 1624 KB Output is correct
25 Correct 6 ms 1628 KB Output is correct
26 Correct 8 ms 1628 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 72908 KB Output is correct
2 Correct 795 ms 73008 KB Output is correct
3 Correct 766 ms 72532 KB Output is correct
4 Correct 695 ms 72788 KB Output is correct
5 Correct 689 ms 63552 KB Output is correct
6 Correct 799 ms 72484 KB Output is correct
7 Correct 770 ms 70992 KB Output is correct
8 Correct 749 ms 71764 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 798 ms 24440 KB Output is correct
3 Correct 2878 ms 72820 KB Output is correct
4 Correct 2848 ms 72680 KB Output is correct
5 Execution timed out 3041 ms 68976 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 72736 KB Output is correct
2 Correct 603 ms 72792 KB Output is correct
3 Execution timed out 3064 ms 70740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 5 ms 1624 KB Output is correct
20 Correct 5 ms 1628 KB Output is correct
21 Correct 7 ms 1628 KB Output is correct
22 Correct 8 ms 1628 KB Output is correct
23 Correct 37 ms 1620 KB Output is correct
24 Correct 8 ms 1624 KB Output is correct
25 Correct 6 ms 1628 KB Output is correct
26 Correct 8 ms 1628 KB Output is correct
27 Correct 14 ms 2648 KB Output is correct
28 Correct 13 ms 2804 KB Output is correct
29 Correct 14 ms 2652 KB Output is correct
30 Correct 38 ms 2652 KB Output is correct
31 Correct 18 ms 2648 KB Output is correct
32 Correct 18 ms 2648 KB Output is correct
33 Correct 173 ms 24452 KB Output is correct
34 Correct 169 ms 24484 KB Output is correct
35 Correct 204 ms 24400 KB Output is correct
36 Correct 316 ms 24400 KB Output is correct
37 Correct 309 ms 24404 KB Output is correct
38 Correct 378 ms 24472 KB Output is correct
39 Correct 892 ms 14952 KB Output is correct
40 Correct 828 ms 15116 KB Output is correct
41 Correct 853 ms 14968 KB Output is correct
42 Correct 389 ms 15124 KB Output is correct
43 Correct 175 ms 24404 KB Output is correct
44 Correct 162 ms 24404 KB Output is correct
45 Correct 161 ms 24400 KB Output is correct
46 Correct 164 ms 24444 KB Output is correct
47 Correct 159 ms 24404 KB Output is correct
48 Correct 159 ms 24400 KB Output is correct
49 Correct 161 ms 24404 KB Output is correct
50 Correct 156 ms 24424 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 5 ms 1624 KB Output is correct
20 Correct 5 ms 1628 KB Output is correct
21 Correct 7 ms 1628 KB Output is correct
22 Correct 8 ms 1628 KB Output is correct
23 Correct 37 ms 1620 KB Output is correct
24 Correct 8 ms 1624 KB Output is correct
25 Correct 6 ms 1628 KB Output is correct
26 Correct 8 ms 1628 KB Output is correct
27 Correct 745 ms 72908 KB Output is correct
28 Correct 795 ms 73008 KB Output is correct
29 Correct 766 ms 72532 KB Output is correct
30 Correct 695 ms 72788 KB Output is correct
31 Correct 689 ms 63552 KB Output is correct
32 Correct 799 ms 72484 KB Output is correct
33 Correct 770 ms 70992 KB Output is correct
34 Correct 749 ms 71764 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 798 ms 24440 KB Output is correct
37 Correct 2878 ms 72820 KB Output is correct
38 Correct 2848 ms 72680 KB Output is correct
39 Execution timed out 3041 ms 68976 KB Time limit exceeded
40 Halted 0 ms 0 KB -