Submission #439220

#	Time	Username	Problem	Language	Result	Execution time	Memory
439220		kig9981	IOI Fever (JOI21_fever)	C++17	100 / 100	1592 ms	33920 KiB

fever

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

vector<int> x[4], X[4][100000];
vector<pair<int,int>> P;
int R[100000][8], dist[100000][8];

inline int get_d(int p, int d)
{
	switch(d&=3) {
		case 0: return P[p].first+P[p].second;
		case 1: return P[p].second;
		case 2: return P[p].first-P[p].second;
		case 3: return P[p].first;
	}
	return -1;
}

inline int get_d(int p)
{
	if(P[p].first>0) {
		if(P[p].second>=P[p].first) return 7;
		if(P[p].second<=-P[p].first) return 3;
		return 5;
	}
	if(P[p].second>-P[p].first) return 7;
	if(P[p].second<P[p].first) return 3;
	return 1;
}

inline int get_dist(int a, int b)
{
	if(P[a].first==P[b].first) return abs(P[a].second-P[b].second)>>1;
	if(P[a].second==P[b].second) return abs(P[a].first-P[b].first)>>1;
	return abs(P[a].first-P[b].first);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, ans=0, nxt[3], n;
	priority_queue<tuple<int,int,int>> Q;
	auto cmp=[&](int a, int b) {
		return P[a]<P[b];
	};
	auto cmp2=[&](pair<int,int> a, int b) {
		return a<P[b];
	};
	auto cmp3=[&](int a, pair<int,int> b) {
		return P[a]<b;
	};
	cin>>N; P.resize(N);
	for(int i=0;i<N;i++) {
		cin>>P[i].first>>P[i].second;
		P[i].first<<=1;
		P[i].second<<=1;
		if(i) {
			P[i].first-=P[0].first;
			P[i].second-=P[0].second;
		}
	}
	P[0]={0,0};
	for(int t=0;t<4;t++) {
		int res=0;
		memset(dist,0x7f,sizeof(dist));
		memset(R,-1,sizeof(R));
		for(int d=0;d<2;d++) Q.emplace(dist[0][d]=0,0,d);
		for(int d=0;d<4;d++) {
			x[d].clear();
			for(int i=0;i<N;i++) {
				x[d].push_back(get_d(i,d));
				X[d][i].clear();
			}
			sort(x[d].begin(),x[d].end()); x[d].resize(unique(x[d].begin(),x[d].end())-x[d].begin());
			for(int i=0;i<N;i++) X[d][lower_bound(x[d].begin(),x[d].end(),get_d(i,d))-x[d].begin()].push_back(i);
			for(int i=0;i<x[d].size();i++) {
				sort(X[d][i].begin(),X[d][i].end(),cmp);
				for(int j=1;j<X[d][i].size();j++) {
					R[X[d][i][j-1]][d]=X[d][i][j];
					R[X[d][i][j]][d|4]=X[d][i][j-1];
				}
			}
		}
		while(!Q.empty()) {
			auto[t,c,d]=Q.top();
			Q.pop();
			if(-t!=dist[c][d]) continue;
			nxt[0]=get_d(c);
			nxt[1]=nxt[0]-1;
			nxt[2]=(nxt[0]+1)&7;
			for(auto nd: nxt) {
				int j, dd=lower_bound(x[nd&3].begin(),x[nd&3].end(),get_d(c,nd))-x[nd&3].begin();
				if(nd&4) {
					if(nd==7) j=upper_bound(X[nd&3][dd].begin(),X[nd&3][dd].end(),make_pair(P[c].first,P[c].second-(dist[c][d]<<(nd&1))),cmp2)-X[nd&3][dd].begin()-1;
					else j=upper_bound(X[nd&3][dd].begin(),X[nd&3][dd].end(),make_pair(P[c].first-(dist[c][d]<<(nd&1)),0x7fffffff),cmp2)-X[nd&3][dd].begin()-1;
				}
				else {
					if(nd==3) j=lower_bound(X[nd][dd].begin(),X[nd][dd].end(),make_pair(P[c].first,P[c].second+(dist[c][d]<<(nd&1))),cmp3)-X[nd][dd].begin();
					else j=lower_bound(X[nd][dd].begin(),X[nd][dd].end(),make_pair(P[c].first+(dist[c][d]<<(nd&1)),-0x7fffffff),cmp3)-X[nd][dd].begin();
				}
				if(0<=j && j<X[nd&3][dd].size() && dist[n=X[nd&3][dd][j]][nd]>get_dist(c,n)) Q.emplace(-(dist[n][nd]=get_dist(c,n)),n,nd);
			}
			if((n=R[c][d])>-1 && dist[n][d]>dist[c][d]+get_dist(c,n)) Q.emplace(-(dist[n][d]=dist[c][d]+get_dist(c,n)),n,d);
		}
		for(int i=0;i<N;i++) for(int j=0;j<8;j++) if(dist[i][j]<0x7f7f7f7f) {
			res++;
			break;
		}
		ans=max(ans,res);
		for(auto &[x,y]: P) tie(x,y)=make_pair(y,-x);
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for(int i=0;i<x[d].size();i++) {
      |                ~^~~~~~~~~~~~
fever.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int j=1;j<X[d][i].size();j++) {
      |                 ~^~~~~~~~~~~~~~~
fever.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     if(0<=j && j<X[nd&3][dd].size() && dist[n=X[nd&3][dd][j]][nd]>get_dist(c,n)) Q.emplace(-(dist[n][nd]=get_dist(c,n)),n,nd);
      |                ~^~~~~~~~~~~~~~~~~~~
fever.cpp:114:46: warning: operation on 'n' may be undefined [-Wsequence-point]
  114 |     if(0<=j && j<X[nd&3][dd].size() && dist[n=X[nd&3][dd][j]][nd]>get_dist(c,n)) Q.emplace(-(dist[n][nd]=get_dist(c,n)),n,nd);

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