Submission #793204

#	Time	Username	Problem	Language	Result	Execution time	Memory
793204		Dan4Life	IOI Fever (JOI21_fever)	C++17	37 / 100	671 ms	25108 KiB

fever

#include <bits/stdc++.h>
using namespace std;
vector<array<int,3>> v;
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], b[mxN];

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 ti(int i, int j){
	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 dis;
}

int main(){
	cin >> n; b[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(b+1,b+n,0); v.clear();
		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 = i+1; j < n; j++)
				if(ti(i,j)!=-1) v.push_back({ti(i,j),i,j});
		sort(begin(v),end(v));
		for(auto [t,i,j] : v) b[i]=b[j]=(b[i]|b[j]); 
		ans = max(ans, accumulate(b,b+n,0));
		for(int i = 1; i < n; i++)swap(x[i],y[i]),y[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