제출 #1228659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228659		vuavisao	Naval battle (CEOI24_battle)	C++20	46 / 100	3030 ms	793876 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 = other.y - this->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 = other.y - this->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;

namespace sub4 {
	bool check() {
		return (n <= 200);
	}

	bool mark[N];

	void solve() {
		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';
	}
}

namespace sub5 {
	int mark[N];

	void solve() {
		for (int i = 1; i <= n; ++i) mark[i] = INF;
		vector<tuple<int, int, int>> events;
		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 >= INF) continue;
				events.push_back(make_tuple(dist, l.idx, r.idx));
			}
		}
		sort(events.begin(), events.end());
		for (int i = 0, j = 0; i < events.size(); i = j) {
			while (j < events.size() && get<0>(events[i]) == get<0>(events[j])) ++j;
			for (int k = i; k < j; ++k) {
				const auto& [dist, l, r] = events[k];
				if (mark[l] < dist || mark[r] < dist) {
					continue;
				}
				mark[l] = mark[r] = dist;
			}
		}
		for (int i = 1; i <= n; ++i) {
			if (mark[i] >= INF) {
				cout << i << '\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));
	}
	sub5::solve();
	return (0 ^ 0);
}

/// Code by vuavisao

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