Submission #734362

#	Time	Username	Problem	Language	Result	Execution time	Memory
734362		QwertyPi	IOI Fever (JOI21_fever)	C++14	37 / 100	5068 ms	60560 KiB

fever

#include <bits/stdc++.h>

using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int INF = 1 << 30;
struct point{
	int x, y, d, id;
};

vector<point> P;

int front(set<pair<int, int>>& s){
	if(s.empty()) return -1;
	return s.begin()->second;
}

int back(set<pair<int, int>>& s){ 
	if(s.empty()) return -1;
	return (--s.end())->second;
}

int collide(int a, int b){
	if(P[a].d == P[b].d) return INF;
	if((P[a].d ^ P[b].d) == 1){
		switch(P[a].d){
			case 0: return P[a].y == P[b].y && P[a].x < P[b].x ? (P[b].x - P[a].x) / 2 : INF;
			case 1: return P[a].y == P[b].y && P[b].x < P[a].x ? (P[a].x - P[b].x) / 2 : INF;
			case 2: return P[a].x == P[b].x && P[a].y < P[b].y ? (P[b].y - P[a].y) / 2 : INF;
			case 3: return P[a].x == P[b].x && P[b].y < P[a].y ? (P[a].y - P[b].y) / 2 : INF;
		}
		return INF;
	}
	if(abs(P[a].x - P[b].x) != abs(P[a].y - P[b].y)) return INF;
	int D = abs(P[a].x - P[b].x);
	if(P[a].x + P[a].y == P[b].x + P[b].y){
		if(P[a].x > P[b].x) swap(a, b);
		if((P[a].d == 0 && P[b].d == 2) || (P[a].d == 3 && P[b].d == 1)) return D;
		return INF;
	}else{
		if(P[a].x > P[b].x) swap(a, b);
		if((P[a].d == 0 && P[b].d == 3) || (P[a].d == 2 && P[b].d == 1)) return D;
		return INF;
	}
}

int calc(){
	map<int, set<pair<int, int>>> X[4], Y[4], A[4], M[4];
	for(auto p : P){
		X[p.d][p.x].insert({p.y, p.id});
		Y[p.d][p.y].insert({p.x, p.id});
		A[p.d][p.x + p.y].insert({p.x - p.y, p.id});
		M[p.d][p.x - p.y].insert({p.x + p.y, p.id});
	}
	vector<int> T(P.size(), INF);
	
	auto erase = [&](int id, int t){
		auto& p = P[id]; T[id] = t;
		X[p.d][p.x].erase({p.y, p.id});
		Y[p.d][p.y].erase({p.x, p.id});
		A[p.d][p.x + p.y].erase({p.x - p.y, p.id});
		M[p.d][p.x - p.y].erase({p.x + p.y, p.id});
	};
	
	auto check = [&](int d, set<pair<int, int>>& s, int t){
		int id, timer;
		while(id = front(X[d][P[t].x]), timer = collide(id, t), timer != INF) erase(id, timer); 
		while(id = back(X[d][P[t].x]), timer = collide(id, t), timer != INF) erase(id, timer); 
	};
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, 0}); T[0] = 0;
	while(!pq.empty()){
		auto [t, v] = pq.top(); pq.pop();
		if(T[v] != t) continue;
		for(int i = 0; i < P.size(); i++){
			int nt = collide(v, i);
			if(T[v] <= nt && nt < T[i]){
				T[i] = nt; pq.push({nt, i});
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < P.size(); i++){
		if(T[i] != INF){
			ans++;
		}
	}
	return ans;
}

int32_t main(){
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		int x, y; cin >> x >> y; x *= 2, y *= 2;
		P.push_back({x, y, 0, i});
	}
	int ans = 0;
	for(int d0 = 0; d0 < 4; d0++){
		P[0].d = d0;
		for(int i = 1; i < n; i++){
			P[i].d = -1;
			int dx = P[i].x - P[0].x;
			int dy = P[i].y - P[0].y;
			if(dx == 0){
				P[i].d = 2 ^ (dy > 0);
			}else if(dy == 0){
				P[i].d = 0 ^ (dx > 0);
			}else{
				if(abs(dx) < abs(dy)){
					P[i].d = 2 ^ (dy > 0);
				}else if(abs(dy) < abs(dx)){
					P[i].d = 0 ^ (dx > 0);
				}else{
					if(P[0].d == 0 || P[0].d == 1) {
						if((P[0].d == 0) == (dx > 0)) P[i].d = 2 ^ (dy > 0);
						else P[i].d = P[0].d;
					}
					if(P[0].d == 2 || P[0].d == 3) {
						if((P[0].d == 2) == (dy > 0)) P[i].d = 0 ^ (dx > 0);
						else P[i].d = P[0].d;
					}
				}
			}
			assert(P[i].d != -1);
		}
		ans = max(ans, calc());
	}
	cout << ans << endl;
}

Compilation message (stderr)

fever.cpp: In function 'int calc()':
fever.cpp:74:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |   auto [t, v] = pq.top(); pq.pop();
      |        ^
fever.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 0; i < P.size(); i++){
      |                  ~~^~~~~~~~~~
fever.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0; i < P.size(); i++){
      |                 ~~^~~~~~~~~~
fever.cpp:66:7: warning: variable 'check' set but not used [-Wunused-but-set-variable]
   66 |  auto check = [&](int d, set<pair<int, int>>& s, int t){
      |       ^~~~~

• 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