Submission #1221416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221416		onbert	IOI Fever (JOI21_fever)	C++20	37 / 100	5092 ms	49628 KiB

fever

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
    int u, t;
    bool operator < (const thing &b) const {
        return t > b.t;
    }
};

const int maxn = 1e5 + 5, INF = 1e16;
int n;
pair<int,int> a[maxn];
pair<int,int> tran[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int dir[maxn];
bool vis[maxn];

int meet(int u, int v) {
    auto [ux, uy] = a[u];
    auto [vx, vy] = a[v];
    auto [udx, udy] = tran[dir[u]];
    auto [vdx, vdy] = tran[dir[v]];
    if (dir[v] == (dir[u]+1)%4 || dir[v] == (dir[u] + 3)%4) {
        // cout << u << " " << v << " " << (vx - ux) * (udx + vdx) << " " << (vy - uy) * (udy + vdy) << endl;
        if ((vx - ux) * (udx - vdx) == (vy - uy) * (udy - vdy)) {
            int t = (vx - ux) * (udx - vdx);
            // cout << u << " " << v << " " << t << endl;
            if (t >= 0) return t;
        }
    } else if (dir[v] == (dir[u]+2)%4) {
        int vt = - ux * udx - vx * vdx - uy * udy - vy * vdy;
        if (vt == abs(ux - vx) + abs(uy - vy)) return vt / 2;
    }
    return -1;
}

int solve() {
    dir[0] = 1;
    auto [x0, y0] = a[0];
    for (int i=1;i<n;i++) {
        auto [x, y] = a[i];
        if (abs(x - x0) == abs(y - y0)) {
            if (x < x0) dir[i] = 1;
            else if (y < y0) dir[i] = 0;
            else if (y > y0) dir[i] = 2;
        } else {
            pair<int,int> mx = {-INF, -INF};
            for (int j=0;j<4;j++) {
                auto [dx, dy] = tran[j];
                mx = max(make_pair((x0 - x) * dx + (y0 - y) * dy, j), mx);
            }
            dir[i] = mx.second;
        }
    }
    
    for (int i=0;i<n;i++) vis[i] = false;
    priority_queue<thing> pq;
    pq.push({0, 0});
    while (pq.size()) {
        auto [u, t] = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        auto [ux, uy] = a[u];
        for (int v=0;v<n;v++) if (!vis[v]) {
            auto [vx, vy] = a[v];
            int vt = meet(u, v);
            if (vt != -1 && vt >= t) pq.push({v, vt});
        }
    }

    int ret = 0;
    for (int i=0;i<n;i++) ret += vis[i];
    return ret;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i=0;i<n;i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x * 2, y * 2};
    }
    int ans = 0;
    for (int ii=0;ii<4;ii++) {
        ans = max(solve(), ans);
        for (int i=1;i<n;i++) {
            int newx = a[0].first + (a[i].second - a[0].second);
            int newy = a[0].second - (a[i].first - a[0].first);
            a[i] = {newx, newy};
        }
    }
    cout << ans << "\n";
}

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