Hướng dẫn giải của [2425 KS1] Bài 2: Chia gạo
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có N đường đứng và M đường ngang tạo N x M giao điểm, đặt 1 túi gạo tại mỗi giao điểm. Đếm số túi trong đường tròn (ranh giới tính là bên trong), đáp án là |NM - 2*trong|.
Sub 1: Vét cạn, ~N, M \le 2000~ ~O(N \cdot M)~
Xét từng giao điểm. Chạy riêng subtask này đạt 15/20 test.
Sub 2: Nhị phân, ~N, M \le 5 \cdot 10^4~ ~O(N \log M)~
Với mỗi đường đứng, tính độ cao đường tròn và đếm bằng nhị phân số đường ngang nằm trong. Chạy riêng subtask này đạt 20/20 test.
Chương trình hoàn chỉnh
Nếu N, M <= 2000 dùng sub 1, ngược lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, M, x, y, R;
vector<ll> X, Y;
ll isqrtll(ll v) {
ll t = (ll)sqrtl((long double)v);
while (t * t > v) t--;
while ((t + 1) * (t + 1) <= v) t++;
return t;
}
// Sub 1: vet can O(N*M), dung khi N, M <= 2000: xet tung giao diem
// Diem tren duong tron tinh la ben trong (Cuoi lay phan con lai)
void sub1() {
ll inside = 0;
for (ll xi : X)
for (ll yj : Y) {
ll dx = xi - x, dy = yj - y;
if (dx * dx + dy * dy <= R * R) inside++;
}
ll total = N * M;
cout << llabs(total - 2 * inside) << "\n";
}
// Sub 2: O(N log M): voi moi duong dung, dem bang nhi phan so duong ngang nam trong duong tron
void sub2() {
sort(Y.begin(), Y.end());
ll inside = 0;
for (ll xi : X) {
ll dx = xi - x;
ll D = R * R - dx * dx;
if (D < 0) continue;
ll t = isqrtll(D);
auto lo = lower_bound(Y.begin(), Y.end(), y - t);
auto hi = upper_bound(Y.begin(), Y.end(), y + t);
inside += hi - lo;
}
ll total = N * M;
cout << llabs(total - 2 * inside) << "\n";
}
int main() {
cin >> N >> M >> x >> y >> R;
X.resize(N);
Y.resize(M);
for (auto& v : X) cin >> v;
for (auto& v : Y) cin >> v;
if (N <= 2000 && M <= 2000) sub1();
else sub2();
return 0;
}
Bình luận