Submission #617336

#	Time	Username	Problem	Language	Result	Execution time	Memory
617336		errorgorn	IOI Fever (JOI21_fever)	C++17	37 / 100	5088 ms	74408 KiB

fever

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
ii arr[100005];

const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int dir[100005];

bool inf[100005];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	
	rep(x,n,0) arr[x].fi-=arr[0].fi,arr[x].se-=arr[0].se;
	
	int ans=0;
	rep(zzz,0,4){
		rep(x,0,n){
			if (abs(arr[x].fi)==abs(arr[x].se)){
				if (arr[x].fi>=0) dir[x]=0;
				else if (arr[x].se<0) dir[x]=3;
				else dir[x]=2;
			}
			else if (abs(arr[x].fi)>abs(arr[x].se)){
				if (arr[x].fi>0) dir[x]=0;
				else dir[x]=1; 
			}
			else{
				if (arr[x].se>0) dir[x]=2;
				else dir[x]=3;
			}
		}
		
		//rep(x,0,n){
			//cout<<arr[x].fi<<" "<<arr[x].se<<" "<<dir[x]<<endl;
		//}
		//cout<<endl;
		
		vector<iii> proc;
		rep(x,0,n) rep(y,0,n) if (dir[x]/2==0 && dir[y]/2==1){
			int t1=(arr[y].fi-arr[x].fi)/dx[dir[x]];
			int t2=(arr[x].se-arr[y].se)/dy[dir[y]];
			
			if (t1==t2) proc.pub({2*t1,x,y});
		}
		rep(x,0,n) rep(y,0,n) if (dir[x]==1 && dir[y]==0){
			if (arr[x].se==arr[y].se && arr[x].fi<arr[y].fi){
				proc.pub({arr[y].fi-arr[x].fi,x,y});
			}
		}
		rep(x,0,n) rep(y,0,n) if (dir[x]==3 && dir[y]==2){
			if (arr[x].fi==arr[y].fi && arr[x].se<arr[y].se){
				proc.pub({arr[y].se-arr[x].se,x,y});
			}
		}
		
		memset(inf,false,sizeof(inf));
		inf[0]=true;
		
		sort(all(proc));
		for (auto [a,b,c]:proc) inf[b]=inf[c]=inf[b]|inf[c];
		
		int curr=0;
		rep(x,0,n) curr+=inf[x];
		
		ans=max(ans,curr);
		
		rep(x,0,n) swap(arr[x].fi,arr[x].se),arr[x].fi*=-1;
	}
	
	cout<<ans<<endl;
}

• 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