Submission #386287

#	Time	Username	Problem	Language	Result	Execution time	Memory
386287		model_code	IOI Fever (JOI21_fever)	C++17	100 / 100	1436 ms	128400 KiB

fever

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

// 入力など
long long N;
long long X[1 << 17], Y[1 << 17];
long long dir[1 << 19];

// 座標圧縮
vector<long long> GX, GY, GPLUS, GMINS;
vector<tuple<long long, long long, int>> PX[100009][4];
vector<tuple<long long, long long, int>> PY[100009][4];
vector<tuple<long long, long long, int>> PPLUS[100009][4];
vector<tuple<long long, long long, int>> PMINS[100009][4];
long long PLUS[1 << 17], MINS[1 << 17];

// シミュレーション
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
vector<pair<long long, int>> G[1 << 19];
long long dist[1 << 19], final_dst[1 << 19];
bool used[1 << 19];
bool used2[1 << 19];

// その他
int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

void init() {
	GX.clear(); GY.clear(); GPLUS.clear(); GMINS.clear();
	for (int i = 0; i < 100009; i++) {
		PLUS[i] = 0; MINS[i] = 0;
		for (int j = 0; j < 4; j++) {
			PX[i][j].clear(); PY[i][j].clear();
			PPLUS[i][j].clear(); PMINS[i][j].clear();
		}
	}
	for (int i = 0; i < (1 << 19); i++) {
		G[i].clear(); dist[i] = 0;
		used[i] = false; used2[i] = false;
	}
}

long long dst(int p1, int p2) {
	return abs(GX[X[p1]] - GX[X[p2]]) + abs(GY[Y[p1]] - GY[Y[p2]]);
}

void henhari(vector<tuple<long long, long long, int>> v, vector<int> t1, vector<int> t2) {
	int pre1 = -1, pre2 = -1;
	for (int i = 0; i < v.size(); i++) {
		int idx = get<2>(v[i]);
		if (t1[dir[idx]] == 1) {
			if (pre1 != -1) G[pre1 * 3 + t2[dir[idx]]].push_back(make_pair(idx * 3 + t2[dir[idx]], dst(pre1, idx) / 2));
			pre1 = idx;
		}
		if (t1[dir[idx]] == 2) {
			if (pre2 != -1) G[idx * 3 + t2[dir[idx]]].push_back(make_pair(pre2 * 3 + t2[dir[idx]], dst(pre2, idx) / 2));
			pre2 = idx;
		}
	}
}

void adds(long long tm, int pos, int ty) {
	long long ux = GX[X[pos]];
	long long uy = GY[Y[pos]];
	long long vx = GX[X[pos]] + tm * dx[dir[pos]] * 2LL;
	long long vy = GY[Y[pos]] + tm * dy[dir[pos]] * 2LL;

	if (ty == -1) {
		int nex = -1;
		if (dir[pos] == 0) {
			int pos1 = lower_bound(PMINS[MINS[pos]][3].begin(), PMINS[MINS[pos]][3].end(), make_tuple(ux + tm, 0, 0)) - PMINS[MINS[pos]][3].begin();
			if (pos1 < PMINS[MINS[pos]][3].size()) nex = get<2>(PMINS[MINS[pos]][3][pos1]);
		}
		if (dir[pos] == 2) {
			int pos1 = lower_bound(PPLUS[PLUS[pos]][0].begin(), PPLUS[PLUS[pos]][0].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PPLUS[PLUS[pos]][0].begin(); pos1--;
			if (pos1 >= 0) nex = get<2>(PPLUS[PLUS[pos]][0][pos1]);
		}
		if (dir[pos] == 4) {
			int pos1 = lower_bound(PMINS[MINS[pos]][1].begin(), PMINS[MINS[pos]][1].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PMINS[MINS[pos]][1].begin(); pos1--;
			if (pos1 >= 0) nex = get<2>(PMINS[MINS[pos]][1][pos1]);
		}
		if (dir[pos] == 6) {
			int pos1 = lower_bound(PPLUS[PLUS[pos]][2].begin(), PPLUS[PLUS[pos]][2].end(), make_tuple(ux + tm, 0, 0)) - PPLUS[PLUS[pos]][2].begin();
			if (pos1 < PPLUS[PLUS[pos]][2].size()) nex = get<2>(PPLUS[PLUS[pos]][2][pos1]);
		}
		if (nex != -1) {
			long long dsts = dst(pos, nex) / 2LL;
			if (dist[nex * 3 + 2] > dsts) {
				dist[nex * 3 + 2] = dsts;
				Q.push(make_pair(dist[nex * 3 + 2], nex * 3 + 2));
			}
		}
	}
	if (ty == 0) {
		int nex = -1;
		if (dir[pos] == 0) {
			int pos1 = lower_bound(PY[Y[pos]][2].begin(), PY[Y[pos]][2].end(), make_tuple(vx, vy, 0)) - PY[Y[pos]][2].begin();
			if (pos1 < PY[Y[pos]][2].size()) nex = get<2>(PY[Y[pos]][2][pos1]);
		}
		if (dir[pos] == 2) {
			int pos1 = lower_bound(PX[X[pos]][3].begin(), PX[X[pos]][3].end(), make_tuple(vx, vy, 0)) - PX[X[pos]][3].begin();
			if (pos1 < PX[X[pos]][3].size()) nex = get<2>(PX[X[pos]][3][pos1]);
		}
		if (dir[pos] == 4) {
			int pos1 = lower_bound(PY[Y[pos]][0].begin(), PY[Y[pos]][0].end(), make_tuple(vx, vy, (1 << 30))) - PY[Y[pos]][0].begin(); pos1--;
			if (pos1 >= 0) nex = get<2>(PY[Y[pos]][0][pos1]);
		}
		if (dir[pos] == 6) {
			int pos1 = lower_bound(PX[X[pos]][1].begin(), PX[X[pos]][1].end(), make_tuple(vx, vy, (1 << 30))) - PX[X[pos]][1].begin(); pos1--;
			if (pos1 >= 0) nex = get<2>(PX[X[pos]][1][pos1]);
		}
		if (nex != -1) {
			long long dsts = dst(pos, nex) / 2LL;
			if (dist[nex * 3 + 1] > dsts) {
				dist[nex * 3 + 1] = dsts;
				Q.push(make_pair(dist[nex * 3 + 1], nex * 3 + 1));
			}
		}
	}
	if (ty == 1) {
		int nex = -1;
		if (dir[pos] == 0) {
			int pos1 = lower_bound(PPLUS[PLUS[pos]][1].begin(), PPLUS[PLUS[pos]][1].end(), make_tuple(ux + tm, 0, 0)) - PPLUS[PLUS[pos]][1].begin();
			if (pos1 < PPLUS[PLUS[pos]][1].size()) nex = get<2>(PPLUS[PLUS[pos]][1][pos1]);
		}
		if (dir[pos] == 2) {
			int pos1 = lower_bound(PMINS[MINS[pos]][2].begin(), PMINS[MINS[pos]][2].end(), make_tuple(ux + tm, 0, 0)) - PMINS[MINS[pos]][2].begin();
			if (pos1 < PMINS[MINS[pos]][2].size()) nex = get<2>(PMINS[MINS[pos]][2][pos1]);
		}
		if (dir[pos] == 4) {
			int pos1 = lower_bound(PPLUS[PLUS[pos]][3].begin(), PPLUS[PLUS[pos]][3].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PPLUS[PLUS[pos]][3].begin(); pos1--;
			if (pos1 >= 0) nex = get<2>(PPLUS[PLUS[pos]][3][pos1]);
		}
		if (dir[pos] == 6) {
			int pos1 = lower_bound(PMINS[MINS[pos]][0].begin(), PMINS[MINS[pos]][0].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PMINS[MINS[pos]][0].begin(); pos1--;
			if (pos1 >= 0) nex = get<2>(PMINS[MINS[pos]][0][pos1]);
		}
		if (nex != -1) {
			long long dsts = dst(pos, nex) / 2LL;
			if (dist[nex * 3 + 0] > dsts) {
				dist[nex * 3 + 0] = dsts;
				Q.push(make_pair(dist[nex * 3 + 0], nex * 3 + 0));
			}
		}
	}
}

long long solve() {
	init();

	// Step A. 向きを決める
	dir[0] = 0;
	for (int i = 1; i < N; i++) {
		if (X[i] > X[0] && abs(X[i] - X[0]) > abs(Y[i] - Y[0])) dir[i] = 4;
		else if (X[i] < X[0] && abs(X[i] - X[0]) >= abs(Y[i] - Y[0])) dir[i] = 0;
		else if (Y[i] > Y[0]) dir[i] = 6;
		else dir[i] = 2;
	}

	// Step B. 座標圧縮する
	for (int i = 0; i < N; i++) PLUS[i] = X[i] + Y[i];
	for (int i = 0; i < N; i++) MINS[i] = X[i] - Y[i];
	for (int i = 0; i < N; i++) GX.push_back(X[i]);
	for (int i = 0; i < N; i++) GY.push_back(Y[i]);
	for (int i = 0; i < N; i++) GPLUS.push_back(X[i] + Y[i]);
	for (int i = 0; i < N; i++) GMINS.push_back(X[i] - Y[i]);
	sort(GX.begin(), GX.end()); GX.erase(unique(GX.begin(), GX.end()), GX.end());
	sort(GY.begin(), GY.end()); GY.erase(unique(GY.begin(), GY.end()), GY.end());
	sort(GPLUS.begin(), GPLUS.end()); GPLUS.erase(unique(GPLUS.begin(), GPLUS.end()), GPLUS.end());
	sort(GMINS.begin(), GMINS.end()); GMINS.erase(unique(GMINS.begin(), GMINS.end()), GMINS.end());
	for (int i = 0; i < N; i++) X[i] = lower_bound(GX.begin(), GX.end(), X[i]) - GX.begin();
	for (int i = 0; i < N; i++) Y[i] = lower_bound(GY.begin(), GY.end(), Y[i]) - GY.begin();
	for (int i = 0; i < N; i++) PLUS[i] = lower_bound(GPLUS.begin(), GPLUS.end(), PLUS[i]) - GPLUS.begin();
	for (int i = 0; i < N; i++) MINS[i] = lower_bound(GMINS.begin(), GMINS.end(), MINS[i]) - GMINS.begin();

	// Step C. 辺を貼る前準備
	for (int i = 0; i < N; i++) PX[X[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
	for (int i = 0; i < N; i++) PY[Y[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
	for (int i = 0; i < N; i++) PPLUS[PLUS[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
	for (int i = 0; i < N; i++) PMINS[MINS[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
	for (int t = 0; t < 4; t++) {
		for (int i = 0; i < GX.size(); i++) sort(PX[i][t].begin(), PX[i][t].end());
		for (int i = 0; i < GY.size(); i++) sort(PY[i][t].begin(), PY[i][t].end());
		for (int i = 0; i < GPLUS.size(); i++) sort(PPLUS[i][t].begin(), PPLUS[i][t].end());
		for (int i = 0; i < GMINS.size(); i++) sort(PMINS[i][t].begin(), PMINS[i][t].end());
	}

	// Step D. 辺を貼る
	for (int t = 0; t < 4; t++) {
		for (int i = 0; i < GX.size(); i++) henhari(PX[i][t], vector<int>{0, 0, 2, 0, 0, 0, 1, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
		for (int i = 0; i < GY.size(); i++) henhari(PY[i][t], vector<int>{2, 0, 0, 0, 1, 0, 0, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
		for (int i = 0; i < GPLUS.size(); i++) henhari(PPLUS[i][t], vector<int>{2, 0, 1, 0, 1, 0, 2, 0}, vector<int>{2, 1, 0, 1, 2, 1, 0, 1});
		for (int i = 0; i < GMINS.size(); i++) henhari(PMINS[i][t], vector<int>{2, 0, 2, 0, 1, 0, 1, 0}, vector<int>{0, 1, 2, 1, 0, 1, 2, 1});
	}

	// Step E. ダイクストラ法
	for (int i = 0; i < N * 3; i++) dist[i] = (1LL << 60);
	Q.push(make_pair(0, 0));
	Q.push(make_pair(0, 1));
	Q.push(make_pair(0, 2));
	while (!Q.empty()) {
		long long tm = Q.top().first;
		long long pos = Q.top().second; Q.pop();
		if (used2[pos] == false) {
			if (tm != 0) used2[pos] = true;
			for (int i = 0; i < G[pos].size(); i++) {
				int to = G[pos][i].first;
				long long cost = G[pos][i].second;
				if (dist[to] > dist[pos] + cost) {
					dist[to] = dist[pos] + cost;
					Q.push(make_pair(dist[to], to));
				}
			}
		}
		if (used[pos / 3] == false) {
			used[pos / 3] = true;
			adds(tm, pos / 3, -1);
			adds(tm, pos / 3, 0);
			adds(tm, pos / 3, 1);
		}
	}

	for (int i = 0; i < N; i++) X[i] = GX[X[i]];
	for (int i = 0; i < N; i++) Y[i] = GY[Y[i]];
	for (int i = 0; i < N; i++) final_dst[i] = (1LL << 60);
	for (int i = 0; i < N * 3; i++) final_dst[i / 3] = min(final_dst[i / 3], dist[i]);

	int cnt = 0;
	final_dst[0] = 0;
	for (int i = 0; i < N; i++) {
		if (final_dst[i] != (1LL << 60)) cnt += 1;
	}
	return cnt;
}

int main() {
	// Step #1. 入力（0-indexed）
	scanf("%lld", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld%lld", &X[i], &Y[i]);
		X[i] *= 2; Y[i] *= 2;
	}

	// Step #2. 全探索
	long long Answer = 0;
	for (int t = 0; t < 4; t++) {
		long long ret = solve();
		Answer = max(Answer, ret);
		for (int i = 0; i < N; i++) {
			long long sx = X[i], sy = Y[i];
			X[i] = -sy;
			Y[i] = sx;
		}
	}

	// Step #3. 出力
	cout << Answer << endl;
	return 0;
}

Compilation message (stderr)

fever.cpp:9: warning: ignoring #pragma warning  [-Wunknown-pragmas]
    9 | #pragma warning (disable: 4996)
      | 
fever.cpp: In function 'void henhari(std::vector<std::tuple<long long int, long long int, int> >, std::vector<int>, std::vector<int>)':
fever.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
fever.cpp: In function 'void adds(long long int, int, int)':
fever.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    if (pos1 < PMINS[MINS[pos]][3].size()) nex = get<2>(PMINS[MINS[pos]][3][pos1]);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    if (pos1 < PPLUS[PLUS[pos]][2].size()) nex = get<2>(PPLUS[PLUS[pos]][2][pos1]);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    if (pos1 < PY[Y[pos]][2].size()) nex = get<2>(PY[Y[pos]][2][pos1]);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fever.cpp:109:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    if (pos1 < PX[X[pos]][3].size()) nex = get<2>(PX[X[pos]][3][pos1]);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fever.cpp:131:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    if (pos1 < PPLUS[PLUS[pos]][1].size()) nex = get<2>(PPLUS[PLUS[pos]][1][pos1]);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:135:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |    if (pos1 < PMINS[MINS[pos]][2].size()) nex = get<2>(PMINS[MINS[pos]][2][pos1]);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:71:12: warning: unused variable 'uy' [-Wunused-variable]
   71 |  long long uy = GY[Y[pos]];
      |            ^~
fever.cpp: In function 'long long int solve()':
fever.cpp:189:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |   for (int i = 0; i < GX.size(); i++) sort(PX[i][t].begin(), PX[i][t].end());
      |                   ~~^~~~~~~~~~~
fever.cpp:190:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |   for (int i = 0; i < GY.size(); i++) sort(PY[i][t].begin(), PY[i][t].end());
      |                   ~~^~~~~~~~~~~
fever.cpp:191:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |   for (int i = 0; i < GPLUS.size(); i++) sort(PPLUS[i][t].begin(), PPLUS[i][t].end());
      |                   ~~^~~~~~~~~~~~~~
fever.cpp:192:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |   for (int i = 0; i < GMINS.size(); i++) sort(PMINS[i][t].begin(), PMINS[i][t].end());
      |                   ~~^~~~~~~~~~~~~~
fever.cpp:197:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |   for (int i = 0; i < GX.size(); i++) henhari(PX[i][t], vector<int>{0, 0, 2, 0, 0, 0, 1, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
      |                   ~~^~~~~~~~~~~
fever.cpp:198:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |   for (int i = 0; i < GY.size(); i++) henhari(PY[i][t], vector<int>{2, 0, 0, 0, 1, 0, 0, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
      |                   ~~^~~~~~~~~~~
fever.cpp:199:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |   for (int i = 0; i < GPLUS.size(); i++) henhari(PPLUS[i][t], vector<int>{2, 0, 1, 0, 1, 0, 2, 0}, vector<int>{2, 1, 0, 1, 2, 1, 0, 1});
      |                   ~~^~~~~~~~~~~~~~
fever.cpp:200:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |   for (int i = 0; i < GMINS.size(); i++) henhari(PMINS[i][t], vector<int>{2, 0, 2, 0, 1, 0, 1, 0}, vector<int>{0, 1, 2, 1, 0, 1, 2, 1});
      |                   ~~^~~~~~~~~~~~~~
fever.cpp:213:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |    for (int i = 0; i < G[pos].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
fever.cpp: In function 'int main()':
fever.cpp:245:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  245 |  scanf("%lld", &N);
      |  ~~~~~^~~~~~~~~~~~
fever.cpp:247:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  247 |   scanf("%lld%lld", &X[i], &Y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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