Submission #947339

#	Time	Username	Problem	Language	Result	Execution time	Memory
947339		MilosMilutinovic	IOI Fever (JOI21_fever)	C++14	25 / 100	5070 ms	82444 KiB

fever

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int n;
ll x[100005],y[100005],dir[100005];
bool was[100005],seen[100005];

int main(){
	n=readint();
	for(int i=1;i<=n;i++) x[i]=readint(),y[i]=readint(),x[i]*=2,y[i]*=2;
	int ans=0;
	for(int d=0;d<4;d++){
		for(int i=1;i<=n;i++) was[i]=seen[i]=false;
		dir[1]=d;
		was[1]=true;
		set<pair<ll,int>> st;
		st.emplace(0,1);
		while(!st.empty()){
			auto it=st.begin();
			ll t=it->first;
			int i=it->second;
			st.erase(it);
			if(seen[i]) continue;
			seen[i]=true;
			for(int j=1;j<=n;j++){
				//if(was[j]) continue;
				if(i==j) continue;
				for(int dd=0;dd<4;dd++){
					if(dir[i]==dd) continue;
					ll cx=dx[dir[i]]-dx[dd];
					ll cy=dy[dir[i]]-dy[dd];
					if((x[j]-x[i])*cy!=(y[j]-y[i])*cx) continue;
					ll ct=(cx==0?(y[j]-y[i])/cy:(x[j]-x[i])/cx);
					if(x[i]+ct*dx[dir[i]]!=x[j]+ct*dx[dd]) continue;
					if(y[i]+ct*dy[dir[i]]!=y[j]+ct*dy[dd]) continue;
					if(ct<t) continue;
					dir[j]=dd;
					was[j]=true;
					st.emplace(ct,j);
					//break;
				}
			}
		}
		int cnt=0;
		for(int i=1;i<=n;i++) cnt+=was[i];
		ans=max(ans,cnt);
	}
	printf("%d\n",ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31