Submission #1069272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069272		juicy	IOI Fever (JOI21_fever)	C++17	100 / 100	2436 ms	94816 KiB

fever

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, inf = 1e9 + 7;
const int U = 0, R = 1, D = 2, L = 3;
const int RU = 4, RD = 5, LD = 6, LU = 7;

int n, cnt;
int x[N], y[N], dir[N], ord[N];
array<int, 8> d[N];
bool vis[N];
array<map<int, vector<int>>, 8> mp;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;

void psh(int u, int dr, int c) {
    if (d[u][dr] > c) {
        pq.push({d[u][dr] = c, u, dr});
    }
}

int lower(vector<int> &cands, int x, int *a) {
    int l = 0, r = cands.size() - 1, p = cands.size();
    while (l <= r) {
        int md = (l + r) / 2;
        if (a[cands[md]] <= x) {
            p = md;
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    return p;
}

int higher(vector<int> &cands, int x, int *a) {
    int l = 0, r = cands.size() - 1, p = cands.size();
    while (l <= r) {
        int md = (l + r) / 2;
        if (x <= a[cands[md]]) {
            p = md;
            r = md - 1;
        } else {
            l = md + 1;;
        }
    }
    return p;
} 

void solve(int u, int dr) {
    for (int i = 0; i < 8; ++i) {
        bool valid = !vis[u], pos;
        int k;
        if (i < 4) {
            valid &= i == dir[u];
            pos = i < 2;
            k = i % 2 == 0 ? x[u] : y[u];
        } else {
            valid &= i - 4 == dir[u] || (i - 4 + 1) % 4 == dir[u];
            pos = i < 6;
            k = i % 2 == 0 ? x[u] - y[u] : x[u] + y[u]; 
        }
        auto &cands = mp[i][k];
        int *a = i == U || i == D ? y : x;
        int v = i < 4 ? 1 : 2;
        if (i == dr) {
            auto it = (pos ? higher(cands, a[u], a) : lower(cands, a[u], a)) + 1;
            if (it < cands.size()) {
                psh(cands[it], dr, d[u][dr] + v * abs(a[cands[it]] - a[u]));
            }
        }
        if (valid) {
            int cur = dr == -1 ? 0 : (v == 1 ? d[u][dr] : (d[u][dr] + 1) / 2);
            int it;
            if (pos) {
                it = higher(cands, a[u] + cur, a);
            } else {
                it = lower(cands, a[u] - cur, a);
            }
            if (it < cands.size()) {
                psh(cands[it], i, v * abs(a[cands[it]] - a[u]));
            }
        }
    }
    if (!vis[u]) {
        vis[u] = 1;
        ++cnt;
    }
}

void init() {
    for (int j = 0; j < 8; ++j) {
        map<int, vector<int>>().swap(mp[j]);
    }
    dir[1] = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1) {
            if (abs(x[i] - x[1]) > abs(y[i] - y[1])) {
                dir[i] = x[i] < x[1] ? R : L;
            } else if (abs(y[i] - y[1]) > abs(x[i] - x[1])) {
                dir[i] = y[i] < y[1] ? U : D;
            } else {
                if (x[i] < x[1]) {
                    dir[i] = R;
                } else {
                    dir[i] = y[i] < y[1] ? U : D;
                }
            }
        }
        vis[i] = 0;
        for (int j = 0; j < 8; ++j) {
            d[i][j] = inf;
        }
    }
    sort(ord + 1, ord + n + 1, [&](int i, int j) {
        return tie(x[i], y[i]) < tie(x[j], y[j]);
    });
    for (int i = 1; i <= n; ++i) {
        int u = ord[i];
        mp[U][x[u]].push_back(u);
        mp[R][y[u]].push_back(u);
        mp[RU][x[u] - y[u]].push_back(u);
        mp[RD][x[u] + y[u]].push_back(u);
    }
    for (int i = n; i; --i) {
        int u = ord[i];
        mp[D][x[u]].push_back(u);
        mp[L][y[u]].push_back(u);
        mp[LD][x[u] - y[u]].push_back(u);
        mp[LU][x[u] + y[u]].push_back(u);
    }
}

int qry() {
    init();
    cnt = 0;
    solve(1, -1);
    while (pq.size()) {
        auto [c, u, dr] = pq.top(); pq.pop();
        if (d[u][dr] != c) {
            continue;
        }
        solve(u, dr);
    }
    return cnt;
}

void rot() {
    for (int i = 1; i <= n; ++i) {
        swap(x[i], y[i]);
        x[i] *= -1;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
    } 
    iota(ord + 1, ord + n + 1, 1);
    int res = 0;
    for (int i = 0; i < 4; ++i) {
        res = max(res, qry());
        rot();
    }
    cout << res;
    return 0;
}

Compilation message (stderr)

fever.cpp: In function 'void solve(int, int)':
fever.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if (it < cands.size()) {
      |                 ~~~^~~~~~~~~~~~~~
fever.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             if (it < cands.size()) {
      |                 ~~~^~~~~~~~~~~~~~

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