| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 388698 | SorahISA | IOI Fever (JOI21_fever) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
vector<pii> city;
vector<int> infect, dir;
map<int, vector<pii>> meet; /// (time |-> people meet)
void solve() {
int n; cin >> n, city.resize(n);
for (auto &[x, y] : city) cin >> x >> y;
int x0 = city[0].X, y0 = city[0].Y;
for (auto &[x, y] : city) x -= x0, y -= y0;
auto walk = [&](int id, int t) -> pii {
return {city[id].X + t * (dir[id] == 1) - t * (dir[id] == 2),
city[id].Y + t * (dir[id] == 3) - t * (dir[id] == 4)};
};
int maxAns = 1;
for (int d : {1, 2, 3, 4}) {
/// dir: [+x, -x, +y, -y] ///
infect.assign(n, 0), dir.assign(n, 0), meet.clear();
infect[0] = 1, dir[0] = d;
/// assign directions ///
for (int i = 1; i < n; ++i) {
if (abs(city[i].X) == abs(city[i].Y)) {
if (d == 1) dir[i] = city[i].X > 0 ? (city[i].Y > 0 ? 4 : 3) : 1;
if (d == 2) dir[i] = city[i].X < 0 ? (city[i].Y > 0 ? 4 : 3) : 2;
if (d == 3) dir[i] = city[i].Y > 0 ? (city[i].X > 0 ? 2 : 1) : 3;
if (d == 4) dir[i] = city[i].Y < 0 ? (city[i].X > 0 ? 2 : 1) : 4;
}
if (abs(city[i].X) < abs(city[i].Y)) dir[i] = city[i].Y > 0 ? 4 : 3;
if (abs(city[i].X) > abs(city[i].Y)) dir[i] = city[i].X > 0 ? 2 : 1;
}
/// calculate meet time for every {x, y} ///
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
int dx = abs(city[i].X - city[j].X);
int dy = abs(city[i].Y - city[j].Y);
if (dx == dy and walk(i, dx) == walk(j, dx)) meet[2*dx].eb(i, j);
if (dx == 0 and walk(i, dy) == walk(j, 0) and walk(i, 0) == walk(j, dy)) meet[dy].eb(i, j);
if (dy == 0 and walk(i, dx) == walk(j, 0) and walk(i, 0) == walk(j, dx)) meet[dx].eb(i, j);
}
}
/// check if infection happens ///
for (auto [t, vec] : meet) {
for (int _ = 0; _ < 3; ++_) {
for (auto [x, y] : vec) infect[x] = infect[y] = infect[x] | infect[y];
}
}
maxAns = max(maxAns, accumulate(ALL(infect), 0LL));
// for (int i = 0; i < n; ++i) {
// if (infect[i]) cout << i << "\n";
// }
}
cout << maxAns << "\n";
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}