Submission #571757

#	Time	Username	Problem	Language	Result	Execution time	Memory
571757		8e7	IOI Fever (JOI21_fever)	C++17	37 / 100	5041 ms	58376 KiB

fever

//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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 100005
#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;

struct pnt{
	int x, y, id;
	pnt(){x = y = id = 0;}
	pnt(int a, int b, int c){x = a, y = b, id = c;}
	bool operator ==(const pnt &p){return x == p.x && y == p.y && id == p.id;}
};
pnt a[maxn];
vector<pnt> horz[4][maxn], vert[4][maxn], ru[4][maxn], rd[4][maxn];
bool cmp(const pnt &p, const pnt &q) {
	return p.x == q.x ? (q.y == p.y ? p.id < q.id : p.y < q.y) : p.x < q.x;
}
int LB(vector<pnt> &v, pnt P) {
	return lower_bound(v.begin(), v.end(), P, cmp) - v.begin();
}
int UB(vector<pnt> &v, pnt P) {
	return upper_bound(v.begin(), v.end(), P, cmp) - v.begin();
}
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][3], di[maxn];
bool vis[maxn];

int hi[maxn], vi[maxn], rui[maxn], rdi[maxn];
int main() {
	io
	int n;
	cin >> n;
	{
		vector<int> h, v, u, d;
		for (int i = 0;i < n;i++) {
			cin >> a[i].x >> a[i].y;
			a[i].id = i;
			a[i].x *= 2, a[i].y *= 2;
			h.push_back(a[i].y);
			v.push_back(a[i].x);
			u.push_back(a[i].x - a[i].y);
			d.push_back(a[i].x + a[i].y);
		}
		auto rs = [&] (vector<int> &ve) {
			sort(ve.begin(), ve.end());
			ve.resize(int(unique(ve.begin(), ve.end()) - ve.begin()));
		};
		rs(h), rs(v), rs(u), rs(d);
		debug(h.size(), v.size(), u.size(), d.size());
		for (int i = 0;i < n;i++) {
			hi[i] = lower_bound(h.begin(), h.end(), a[i].y) - h.begin();	
			vi[i] = lower_bound(v.begin(), v.end(), a[i].x) - v.begin();	
			rui[i] = lower_bound(u.begin(), u.end(), a[i].x - a[i].y) - u.begin();	
			rdi[i] = lower_bound(d.begin(), d.end(), a[i].x + a[i].y) - d.begin();	
		}
	}
	int ans = 0;
	for (int init_d = 0;init_d < 4;init_d++) {
		for (int i = 0;i < 4;i++) {
			for (int j = 0;j < maxn;j++)  {
				horz[i][j].clear(), vert[i][j].clear(), ru[i][j].clear(), rd[i][j].clear();
			}
		}
		for (int i = 0;i < n;i++) {
			mind[i][0] = mind[i][1] = mind[i][2] = 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;
			}
			if (di[i] % 2) {
				vert[di[i]][vi[i]].push_back(a[i]);
			} else {
				horz[di[i]][hi[i]].push_back(a[i]);
			}
			ru[di[i]][rui[i]].push_back(a[i]);
			rd[di[i]][rdi[i]].push_back(a[i]);
		}
		for (int i = 0;i < 4;i++) {
			for (int j = 0;j < maxn;j++) {
				sort(horz[i][j].begin(), horz[i][j].end(), cmp);
				sort(vert[i][j].begin(), vert[i][j].end(), cmp);
				sort(ru[i][j].begin(), ru[i][j].end(), cmp);
				sort(rd[i][j].begin(), rd[i][j].end(), cmp);
			}
		}
		mind[0][0] = 0;
		di[0] = init_d;


		auto col = [&] (int i, int j) {
			int dx = a[j].x - a[i].x, dy = a[j].y - a[i].y;			
			int divx = mov[di[i]][0] - mov[di[j]][0], divy = mov[di[i]][1] - mov[di[j]][1];
			if (dx && divx == 0) return -1;	
			if (dy && divy == 0) return -1;	
			if (dx == 0) {
				if (abs(di[i] - di[j]) == 2) return dy / divy;
				return -1;
			}
			if (dy == 0) {
				if (abs(di[i] - di[j]) == 2) return dx / divx;
				return -1;
			}
			if (dx * divy != dy * divx) return -1;
			return dx / divx;
		};
		

		priority_queue<pii, vector<pii>, less<pii> > pq;
		pq.push({0, 0});
		pnt cur;
		int id, prv = 0, ti, nodes = 0;

		auto relax = [&](pnt p, int d, int val) {
			int ind = p.id;
			if (val >= ti && val < mind[ind][d]) {
				mind[ind][d] = val;
				pq.push({val, ind * 3 + d});
			}
		};
		auto upd = [&] (vector<pnt> &se, int it, int d, bool type) {
			pnt p;
			if (type == 0) {
				if (it) {
					p = se[it-1];
				} else {
					return;
				}
			} else {
				if (it != se.size()) {
					p = se[it];
				} else {
					return;
				}
			}
			relax(p, d, col(id, p.id));
		};
		auto to = [&] (vector<pnt> &se, bool type) { //0:prev, 1:next
			int it = LB(se, cur);
			pnt q;	
			if (type && it+1 != se.size()) {
				q = se[it+1];	
			} else if (type == 0 && it) {
				q = se[it-1];
			}
			int val = (abs(q.y - cur.y) + abs(q.x - cur.x)) / 2;
			relax(q, prv, ti + val);
		};

		while (pq.size()) {
			id = pq.top().ss / 3, prv = pq.top().ss % 3;
			ti = pq.top().ff;
			pq.pop();
			if (ti != mind[id][prv]) continue;
			nodes++;
			if (nodes % 1000 == 0) debug(id, prv);
			cur = a[id];
			vis[id] = 1;
			int dir = di[id];
			pnt pos;
			if ((ll)cur.x + mov[dir][0] * 2 * ti < inf) {
				pos = pnt(cur.x + mov[dir][0] * 2 * ti, cur.y + mov[dir][1] * 2 * ti, -1);
				if (dir % 2 == 0) {
					auto se = horz[(dir+2)%4][hi[id]];
					if (dir == 0) upd(se, LB(se, pos), 0, 1);
					else upd(se, UB(se, pos), 0, 0);
				} else {
					auto se = vert[(dir+2)%4][vi[id]];
					if (dir == 1) upd(se, LB(se, pos), 0, 1);
					else upd(se, UB(se, pos), 0, 0);
				}
			}
			pos = pnt(cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti, -1);
			auto se = ru[(3 - dir)][rui[id]];
			if (dir < 2) upd(se, LB(se, pos), 1, 1);
			else upd(se, UB(se, pos), 1, 0);

			pos = pnt(cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti, -1);
			se = rd[(dir < 2 ? 1 - dir : 5 - dir)][rdi[id]];
			if (dir == 0 || dir == 3) upd(se, LB(se, pos), 2, 1);	
			else upd(se, UB(se, pos), 2, 0);	
			
			if (id == 0) continue;
			if (prv == 0) {
				if (dir % 2 == 0) to(horz[dir][hi[id]], dir == 2);
				else to(vert[dir][vi[id]], dir == 3);
			} else if (prv == 1) {
				to(ru[dir][rui[id]], dir >= 2);
			} else {
				to(rd[dir][rdi[id]], dir == 1 || dir == 2);
			}
		}
		int cnt = 0;
		for (int i = 0;i < n;i++) {
			if (vis[i]) cnt++;
		}
		ans = max(ans, cnt);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
fever.cpp:71:3: note: in expansion of macro 'debug'
   71 |   debug(h.size(), v.size(), u.size(), d.size());
      |   ^~~~~
fever.cpp: In lambda function:
fever.cpp:161:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     if (it != se.size()) {
      |         ~~~^~~~~~~~~~~~
fever.cpp: In lambda function:
fever.cpp:172:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |    if (type && it+1 != se.size()) {
      |                ~~~~~^~~~~~~~~~~~
fever.cpp: In function 'int main()':
fever.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
fever.cpp:187:27: note: in expansion of macro 'debug'
  187 |    if (nodes % 1000 == 0) debug(id, prv);
      |                           ^~~~~

• 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