| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 571683 | 8e7 | 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.
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define x first
#define y second
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1e9 + 7;
pii a[maxn];
unordered_map<int, set<pii> > horz, vert, ru, rd;
unordered_map<int, set<pii> > t0, t1, t2, t3;
unordered_map<ll, int> mp;
ll h(pii p) {
return (ll)inf * p.x + p.y;
}
struct pnt{
pii p;
int t, d;
pnt(){t = d = 0;}
pnt(pii P, int ti, int di){p = P, t = ti, d = di;}
};
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int movru[4][2] = {{1, 1}, {1, 1}, {-1, -1}, {-1, -1}};
int movrd[4][2] = {{1, -1}, {-1, 1}, {-1, 1}, {1, -1}};
int mind[maxn], di[maxn];
bool vis[maxn];
int main() {
io
int n;
cin >> n;
for (int i = 0;i < n;i++) {
cin >> a[i].x >> a[i].y;
a[i].x *= 2, a[i].y *= 2;
mp[h(a[i])] = i;
horz[a[i].y].insert(a[i]);
vert[a[i].x].insert(a[i]);
ru[a[i].x - a[i].y].insert(a[i]);
rd[a[i].x + a[i].y].insert(a[i]);
}
t0 = horz, t1 = vert, t2 = ru, t3 = rd;
int ans = 0;
for (int init_d = 0;init_d < 4;init_d++) {
for (int i = 0;i < n;i++) {
mind[i] = inf, vis[i] = 0;
if (i == 0) continue;
int dx = a[i].x - a[0].x, dy = a[i].y - a[0].y;
if (abs(dx) > abs(dy)) {
di[i] = dx > 0 ? 2 : 0;
} else if (abs(dx) < abs(dy)) {
di[i] = dy > 0 ? 3 : 1;
} else {
pii tmp = {dx, dy};
for (int j = 0;j < 4 - init_d;j++) tmp = {-tmp.y, tmp.x};
if (tmp.x > 0) di[i] = tmp.y > 0 ? 3 : 1;
else di[i] = 0;
di[i] = (di[i] + init_d)%4;
}
}
mind[0] = 0;
di[0] = init_d;
horz = t0, vert = t1, ru = t2, rd = t3;
int cnt = 0;
auto rm = [&] (pii p) {
horz[p.y].erase(p);
vert[p.x].erase(p);
ru[p.x - p.y].erase(p);
rd[p.x + p.y].erase(p);
};
pii cur;
auto cl = [&] (set<pii> &se, auto it, int d, int type) {
auto iter = se.begin();
vector<pii> tmp;
if (type == 0) {
while (iter != it) {
tmp.push_back(*iter);
iter = next(iter);
}
} else {
iter = it;
while (iter != se.end()) {
tmp.push_back(*iter);
iter = next(iter);
}
}
for (auto p:tmp) {
int ind = mp[h(p)];
if (d != di[ind]) continue;
assert((abs(cur.x - p.x) + abs(cur.y - p.y)) / 2 >= ti);
mind[ind] = min(mind[ind], (abs(cur.x - p.x) + abs(cur.y - p.y)) / 2);
//debug(ind, d, di[ind]);
//di[ind] = d;
/*
rm(p);
que.push(pnt(p, (abs(cur.x - p.x) + abs(cur.y - p.y) + 1) / 2, d));
*/
}
};
//debug(init_d);
while (true) {
int found = -1, best = inf;
for (int i = 0;i < n;i++) {
if (!vis[i] && mind[i] < best) {
best = mind[i];
found = i;
}
}
if (found == -1) break;
cur = a[found];
vis[found] = 1;
rm(cur);
cnt++;
int ti = mind[found], dir = di[found];
pii pos = {cur.x + mov[dir][0] * ti, cur.y + mov[dir][1] * ti};
if (dir % 2 == 0) {
auto it = horz[cur.y].lower_bound(pos);
if (dir == 0) cl(horz[cur.y], it, 2, 1);
else cl(horz[cur.y], horz[cur.y].lower_bound(pos), 0, 0);
} else {
auto it = vert[cur.x].lower_bound(pos);
if (dir == 1) cl(vert[cur.x], it, 3, 1);
else cl(vert[cur.x], vert[cur.x].upper_bound(pos), 1, 0);
}
pos = {cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti};
auto it = ru[cur.x - cur.y].lower_bound(pos);
auto it2 = ru[cur.x - cur.y].upper_bound(pos);
if (dir == 0) cl(ru[cur.x-cur.y], it, 3, 1);
else if (dir == 1) cl(ru[cur.x-cur.y], it, 2, 1);
else if (dir == 2) cl(ru[cur.x-cur.y], it2, 1, 0);
else cl(ru[cur.x-cur.y], it2, 0, 0);
pos = {cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti};
it = rd[cur.x + cur.y].lower_bound(pos);
it2 = rd[cur.x + cur.y].upper_bound(pos);
if (dir == 0) cl(rd[cur.x + cur.y], it, 1, 1);
else if (dir == 1) cl(rd[cur.x + cur.y], it2, 0, 0);
else if (dir == 2) cl(rd[cur.x + cur.y], it2, 3, 0);
else cl(rd[cur.x + cur.y], it, 2, 1);
}
ans = max(ans, cnt);
}
cout << ans << "\n";
}