Submission #389051

#	Time	Username	Problem	Language	Result	Execution time	Memory
389051		PedroBigMan	IOI Fever (JOI21_fever)	C++14	37 / 100	5100 ms	74416 KiB

fever

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N; cin>>N;
	vector<pl> p; pl cur; 
	REP(i,0,N) {cin>>cur.ff>>cur.ss; if(i!=0) {cur.ff-=p[0].ff; cur.ss-=p[0].ss; p.pb(cur);} else {p.pb(cur);}}
	p[0]={0LL,0LL};
	ll ans=1;
	REP(dir,0,4)
	{
		if(dir!=0)  //rotate 90 deg anticlockwise
		{
			REP(i,0,N) {swap(p[i].ff,p[i].ss); p[i].ff=-p[i].ff;}
		}
		//now guy 1 goes east
		vector<ll> way;
		REP(i,0,N)
		{
			if(i==0) {way.pb(0); continue;}
			if(abs(p[i].ff)>abs(p[i].ss)) 
			{
				if(p[i].ff>0) {way.pb(2);}
				else {way.pb(0);}
			}
			else if(abs(p[i].ff)<abs(p[i].ss))
			{
				if(p[i].ss>0) {way.pb(1);}
				else {way.pb(3);}
			}
			else
			{
				if(p[i].ff>0) {if(p[i].ss>0) {way.pb(1);} else {way.pb(3);}}
				else {way.pb(0);}
			}
		}
		vector<pair<ll,pl> > inter;
		ll x1,y1,x2,y2; ll t;
		REP(i,0,N) 
		{
			REP(j,0,N)
			{
				x1 = p[i].ff; y1 = p[i].ss; x2 = p[j].ff; y2 = p[j].ss;
				if(way[i]==0 && way[j]==1)
				{
					if(x2-x1==y2-y1 && x2-x1>=0) 
					{
						t = 2LL*(x2-x1);
						inter.pb({t,{i,j}});
					}
				}
				else if(way[i]==0 && way[j]==2)
				{
					if(y1==y2 && x2-x1>=0) 
					{
						t = x2-x1;
						inter.pb({t,{i,j}});
					}
				}
				else if(way[i]==0 && way[j]==3)
				{
					if(x2-x1==y1-y2 && x2-x1>=0) 
					{
						t = 2LL*(x2-x1);
						inter.pb({t,{i,j}});
					}
				}
				else if(way[i]==1 && way[j]==2)
				{
					if(x2-x1==y1-y2 && x2-x1>=0) 
					{
						t = 2LL*(x2-x1);
						inter.pb({t,{i,j}});
					}
				}
				else if(way[i]==1 && way[j]==3)
				{
					if(x1==x2 && y1-y2>=0) 
					{
						t = y1-y2;
						inter.pb({t,{i,j}});
					}
				}
				else if(way[i]==2 && way[j]==3)
				{
					if(x1-x2==y1-y2 && x1-x2>=0) 
					{
						t = 2LL*(x1-x2);
						inter.pb({t,{i,j}});
					}
				}
			}
		}
		sort(whole(inter));
		vector<bool> inf; REP(i,0,N) {inf.pb(false);}
		inf[0]=true; 
		ll ind1,ind2;
		REP(i,0,inter.size())
		{
			ind1=inter[i].ss.ff; ind2 = inter[i].ss.ss;
			if(!inf[ind1] && !inf[ind2]) {continue;}
			inf[ind1]=true; inf[ind2]=true;
		}
		ll curans=0; REP(i,0,N) {if(inf[i]) {curans++;}}
		ans=max(ans,curans);
	}
	cout<<ans<<endl;
    return 0;
}

• 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