Submission #388632

#	Time	Username	Problem	Language	Result	Execution time	Memory
388632		SorahISA	IOI Fever (JOI21_fever)	C++17	11 / 100	1 ms	332 KiB

fever

#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, 2, 3, 4}) {
        /// 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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31