oj.uz

Submission #1071012

# Submission time Handle Problem Language Result Execution time Memory
1071012 2024-08-22T23:29:40 Z pawned Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 72672 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);
		bool done = false;
		while (it2 != allx.end() && (*it2).fi <= xh) {
			// do another search inside
			int cx = (*it2).fi;
			vector<pair<ll, ii>> toremove;
			int dx = abs(x - cx);
			// can do up to sqrt for yh
			ll dy = (ll)(pow(4 * (double)(r) * (double)(r) - (double)(dx) * (double)(dx), 0.5) + 1);
			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;
				if (intersect(x, y, cx, cy, r, cr)) {
					done = true;
					toremove.pb(*it3);
					break;
				}
				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--;
			}
			if (done)
				break;
			it2++;
		}
	}
//	cout<<"ANSWER: ";
	for (int x : par)
		cout<<(x + 1)<<" ";
	cout<<endl;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 70740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 451 ms 24328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1095 ms 72672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -