Submission #388617

#TimeUsernameProblemLanguageResultExecution timeMemory
388617SorahISAIOI Fever (JOI21_fever)C++17
11 / 100
1 ms332 KiB
#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) void solve() { int n; cin >> n; vector<pii> city(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; int maxAns = 1; vector<int> infect, dir; map<int, vector<pii>> meet; /// (time |-> people meet) 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)}; }; for (int d = 1; d <= 4; ++d) { /// dir: [+x, -x, +y, -y] /// infect.assign(n, 0), dir.assign(n, 0); 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 or d == 2) dir[i] = city[i].Y > 0 ? 4 : 3; if (d == 3 or d == 4) dir[i] = city[i].X > 0 ? 2 : 1; } 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[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)); } cout << maxAns << "\n"; } int32_t main() { fastIO(); int t = 1; // cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...