Submission #793191

#	Time	Username	Problem	Language	Result	Execution time	Memory
793191		Dan4Life	IOI Fever (JOI21_fever)	C++17	37 / 100	2700 ms	49668 KiB

fever

#include <bits/stdc++.h>
using namespace std;
using ar = array<int,3>;
const int mxN = (int)3e3+10;
const int X[] = {1,0,-1,0,0};
const int Y[] = {0,1,0,-1,0};
int n, d[mxN], x[mxN], y[mxN], sick[mxN];
priority_queue<ar,vector<ar>,greater<ar>> pq;

int D(int i, int di, int j, int dj){
	return abs((x[i]+X[di])-(x[j]+X[dj]))+abs((y[i]+Y[di])-(y[j]+Y[dj]));
}

int getTime(int i, int j){
	if(i==j) return -1;
	int dis = D(i,4,j,4)/2;
	if((x[i]+X[d[i]]*dis)!=(x[j]+X[d[j]]*dis)) return -1;
	if((y[i]+Y[d[i]]*dis)!=(y[j]+Y[d[j]]*dis)) return -1;
	return D(i,4,j,4);
}

int main(){
	cin >> n; sick[0]=1; int ans = 1;
	for(int i = 0; i < n; i++)
		cin >> x[i] >> y[i];
	for(int i = n-1; i >= 0; i--)
		x[i]-=x[0], y[i]-=y[0],x[i]<<=1,y[i]<<=1;
	for(int t = 0; t < 4; t++){
		fill(sick+1,sick+n,0);
		for(int i = 0; i < n; i++){
			if(abs(y[i])<x[i]) d[i] = 2;
			else if(abs(y[i])<=-x[i]) d[i] = 0;
			else if(abs(x[i])<=y[i]) d[i] = 3;
			else if(abs(x[i])<=-y[i]) d[i] = 1;
		}
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(getTime(i,j)!=-1) pq.push({getTime(i,j),i,j});
		while(!empty(pq)){
			auto [t,i,j] = pq.top(); pq.pop();
			if(sick[i]|sick[j]) sick[i]=sick[j]=1; 
		}
		ans = max(ans, accumulate(sick,sick+n,0));
		for(int i = 1; i < n; i++)swap(x[i],y[i]),x[i]*=-1;
	}
	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