Submission #525010

#	Time	Username	Problem	Language	Result	Execution time	Memory
525010		blue	IOI Fever (JOI21_fever)	C++17	37 / 100	5089 ms	40140 KiB

fever

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
 
using mii = map<int, int>;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
 
const int dr = 0;
const int dt = 1;
const int dl = 2;
const int dd = 3;
 
const int INF = 2'000'000'001;
 
 
struct event
{
	int t;
	int i;
	int j;
};
 
vpii delta{{+1, 0}, {0, +1}, {-1, 0}, {0, -1}};
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
 
	int N;
	cin >> N;
 
	int* X = new int[N];
	int* Y = new int[N];
	for(int i = 0; i < N; i++) 
	{
		cin >> X[i] >> Y[i];
		X[i] *= 2;
		Y[i] *= 2;
	}
 
	int res = 1;
 
	for(int i = N-1; i >= 0; i--)
	{
		X[i] -= X[0];
		Y[i] -= Y[0];
	}
 
	for(int t = 0; t < 4; t++)
	{
		// cerr << "\n\n\n\n\n\n\n\n\n\n t = " << t << '\n';		
 
		vi dir(N);
		dir[0] = dt;
 
 
		for(int i = 1; i < N; i++)
		{
			// cerr << i << " <> " << X[i] << ' ' << Y[i] << " : " << int(Y[i] > 0) << ' ' << int(X[i]+Y[i]>0) << ' ' << int(Y[i]-X[i]>0) << '\n';
			if(Y[i] > 0 && X[i]+Y[i] > 0 && Y[i]-X[i] > 0)
				dir[i] = dd;
			else if(Y[i] < 0 && X[i]+Y[i] <= 0 && Y[i]-X[i] <= 0)
				dir[i] = dt;
			else if(X[i] < 0)
				dir[i] = dr;
			else if(X[i] > 0)
				dir[i] = dl;
 
			// cerr << dir[i] << ' ' << dd << '\n';
		}
 
 
 
 
		// cerr << "\n\n\n";
		// for(int i = 0; i < N; i++) cerr << X[i] << ' ' << Y[i] << ' ' << dir[i] << '\n';
 
 
 
		vector<event> E;
 
 
 
 
		for(int i = 0; i < N; i++)
		{
			for(int j = i+1; j < N; j++)
			{
				int t = -1;
				if(X[i] == X[j])
					t = abs(Y[j] - Y[i])/2;
				else if(Y[i] == Y[j])
					t = abs(X[j] - X[i])/2;
				else
					t = abs(X[i] - X[j]);
 
				// cerr << "t = " << t << '\n';
 
				pii di = delta[dir[i]];
				pii dj = delta[dir[j]];
 
				di.first *= t;
				di.second *= t;
 
				dj.first *= t;
				dj.second *= t;
 
 
				// cerr << di.first << ' ' << di.second << ' ' << dj.first << ' ' << dj.second << '\n';
				// cerr << X[i] << ' ' << Y[i] << "  " << X[j] << ' ' << Y[j] << '\n';
 
				di.first += X[i];
				di.second += Y[i];
 
				dj.first += X[j];
				dj.second += Y[j];
 
				// cerr << di.first << ' ' << di.second << ' ' << dj.first << ' ' << dj.second << '\n';
 
 
				if(di == dj && t != -1)
				{
					E.push_back({t, i, j});
				}
			}
		}
		// cerr << "events size = " << sz(E) << '\n';
 
		vi infected(N, 0);
		infected[0] = 1;
 
		sort(E.begin(), E.end(), [] (event u, event v)
		{
			return u.t < v.t;
		});
 
		for(event e : E)
		{
			infected[e.i] = infected[e.j] = (infected[e.i] || infected[e.j]);
		}
 
		int curr = 0;
		for(int i = 0; i < N; i++) curr += infected[i];
 
		res = max(res, curr);
 
 
 
 
	
 
		for(int i = 0; i < N; i++)
		{
			int newX = -Y[i], newY = X[i];
			X[i] = newX;
			Y[i] = newY;
		}
	}
 
	cout << res << '\n';
}

• 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