Submission #1138979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138979		Math4Life2020	IOI Fever (JOI21_fever)	C++20	25 / 100	5092 ms	10428 KiB

fever

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N; const ll Nm = 1e5+5; const ll INF = 1e18;
ll ansG = 0;
vector<ll> x(Nm);
vector<ll> y(Nm);
vector<ll> dir(Nm);
//0=east, 1=north, 2=west, 3=south

pii getv(ll d) { //get vector
	if (d==0) {
		return {1,0};
	} else if (d==1) {
		return {0,1};
	} else if (d==2) {
		return {-1,0};
	} else {
		return {0,-1};
	}
}

ll tcol(pii p0, ll d0, pii p1, ll d1) {
	if (d0==d1) {
		return -1;
	}
	if ((d0^d1)==2) {
		if (d0>d1) {
			swap(d0,d1);
			swap(p0,p1);
		}
		if (d0==0 && d1==2) {
			d0=1; d1=3;
			swap(p1.first,p1.second);
			swap(p0.first,p0.second);
		}
		if (d0==1 && d1==3) {
			if ((p0.first!=p1.first)||(p1.second<p0.second)) {
				return -1;
			}
			return ((p1.second-p0.second+1)/2);
		}
		assert(1==2);
	}
	pii disp = {p1.first-p0.first,p1.second-p0.second};
	if (abs(disp.first)!=abs(disp.second)) {
		return -1;
	}
	pii v0 = getv(d0); pii v1 = getv(d1);
	pii vnet = {v0.first-v1.first,v0.second-v1.second};
	if ((disp.first/vnet.first)>0 && (disp.second/vnet.second)>0) {
		return abs(disp.first);
	} else {
		return -1;
	}
}

void solve() {
	ll ans = 0;
	dir[0]=0;
	for (ll i=1;i<N;i++) {
		if (x[i]>=0) {
			if (y[i]>=x[i]) {
				dir[i]=3;
			} else if (y[i]<=(-x[i])) {
				dir[i]=1;
			} else {
				dir[i]=2;
			}
		} else {
			if (y[i]>(-x[i])) {
				dir[i]=3;
			} else if (y[i]<x[i]) {
				dir[i]=1;
			} else {
				dir[i]=0;
			}
		}
	}
	vector<pii> coord;
	for (ll i=0;i<N;i++) {
		coord.push_back({x[i],y[i]});
	}
	set<pii> s0; //{time, index}
	vector<bool> found(N,false);
	s0.insert({0,0});
	while (!s0.empty()) {
		pii pf = *s0.begin(); s0.erase(s0.begin());
		ll t0 = pf.first; ll x0 = pf.second;
		if (found[x0]) {
			continue;
		}
		found[x0]=1;
		ans++;
		for (ll j=1;j<N;j++) {
			if (!found[j]) {
				ll tc = tcol(coord[x0],dir[x0],coord[j],dir[j]);
				if (tc>=t0) {
					s0.insert({tc,j});
				}
			}
		}
	}
	ansG = max(ans,ansG);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N;
	for (ll i=0;i<N;i++) {
		cin >> x[i] >> y[i];
	}
	for (ll i=(N-1);i>=0;i--) {
		x[i]-=x[0];
		y[i]-=y[0];
	}
	for (ll T=0;T<4;T++) {
		solve();
		vector<ll> x1,y1;
		for (ll i=0;i<N;i++) {
			y1.push_back(x[i]);
			x1.push_back(-y[i]);
		}
		x=x1; y=y1;
	}
	cout << ansG << "\n";
}

• 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