Submission #1228657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228657		vuavisao	Naval battle (CEOI24_battle)	C++20	0 / 100	3095 ms	4936 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 200'000 + 10;
const int INF = 1'000'000'000;

struct Ship {
	int x, y;
	int dir;
	int idx, dir_x, dir_y;
	Ship() {};
	Ship(int _x, int _y, char _dir, int _idx) : x(_x), y(_y), dir(-1), idx(_idx), dir_x(-1), dir_y(-1) {
		if (_dir == 'N') dir = 0, dir_x = 0, dir_y = -1;
		else if (_dir == 'S') dir = 3, dir_x = 0, dir_y = 1;
		else if (_dir == 'E') dir = 2, dir_x = 1, dir_y = 0;
		else if (_dir == 'W') dir = 1, dir_x = -1, dir_y = 0;
	};

	int encounter(const Ship& other) const {
		assert(this->dir >= other.dir);
		if (this->dir == other.dir) return INF;
		if (this->dir == 3 - other.dir) {
			// S - N or E - W
			if (this->dir == 3) {
				if (this->x != other.x || this->y > other.y) return INF;
				// cùng tính chẵn lẻ nên chắc chắn sẽ giao nhau
				return (other.y - this->y) / 2;
			}
			if (this->dir == 2) {
				if (this->y != other.y || this->x > other.x) return INF;
				// cùng tính chẵn lẻ nên chắc chắn sẽ giao nhau
				return (other.x - this->x) / 2;
			}
			assert(false);
		}
		if (this->dir == 3) {
			if (other.dir == 2) {
				/*
					   S(3)
					   !
					   !
				E(2)--->
				*/
				if (this->x <= other.x || this->y >= other.y) return INF;
				int dist_x = this->x - other.x;
				int dist_y = other.y - this->y;
				if (dist_x != dist_y) return INF;
				return dist_x;
			} else if (other.dir == 1) {
				/*
					   S(3)
					   !
					   !
					   <---W(1)
				*/
				if (this->x >= other.x || this->y >= other.y) return INF;
				int dist_x = other.x - this->x;
				int dist_y = other.y - this->y;
				if (dist_x != dist_y) return INF;
				return dist_x;
			}
			assert(false);
		}
		if (this->dir == 2) {
			if (other.dir == 0) {
				/*
				E(2)--->
					   !
					   !
					   N(0)
				*/
				if (this->x <= other.x || this->y <= other.y) return INF;
				int dist_x = other.x - this->x;
				int dist_y = this->y - other.y;
				if (dist_x != dist_y) return INF;
				return dist_x;
			}
			assert(false);
		}
		if (this->dir == 1) {
			if (other.dir == 0) {
				/*
					<---W(1)
					!
					!
					N(0)
				*/
				if (this->x >= other.x || this->y <= other.y) return INF;
				int dist_x = this->x - other.x;
				int dist_y = this->y - other.y;
				if (dist_x != dist_y) return INF;
				return dist_x;
			}
			assert(false);
		}
		assert(false);
	};

	void add(int dist) {
		x += dist * dir_x;
		y += dist * dir_y;
	}

	bool operator>(const Ship& other) const {
		return this->dir > other.dir;
	}
};

int n;
vector<Ship> ships;

bool mark[N];

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n;
	ships.reserve(n);
	for (int i = 1; i <= n; ++i) {
		int x, y; char dir; cin >> x >> y >> dir;
		ships.push_back(Ship(x, y, dir, i));
	}
	while (!ships.empty()) {
		int dist_encounter = INF;
		for (int i = 0; i < ships.size(); ++i) {
			for (int j = i + 1; j < ships.size(); ++j) {
				Ship l = ships[i], r = ships[j];
				if (r > l) swap(l, r);
				int dist = l.encounter(r);
				// if (i == 2 && j == 3) {
				// 	cerr << dist << '\n';
				// }
				if (dist_encounter > dist) {
					dist_encounter = dist;
				}
			}
		}
		for (int i = 0; i < ships.size(); ++i) {
			for (int j = i + 1; j < ships.size(); ++j) {
				Ship l = ships[i], r = ships[j];
				if (r > l) swap(l, r);
				int dist = l.encounter(r);
				if (dist == dist_encounter) {
					mark[l.idx] = mark[r.idx] = true;
				}
			}
		}
		if (dist_encounter >= INF) break;
		vector<Ship> newShips;
		for (auto& ship : ships) {
			if (mark[ship.idx]) continue;
			ship.add(dist_encounter);
			newShips.push_back(ship);
		}
		ships = move(newShips);
	}
	for (const auto &ship : ships) cout << ship.idx << '\n';
	return (0 ^ 0);
}

/// Code by vuavisao

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24