Submission #1229654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229654		vuavisao	Naval battle (CEOI24_battle)	C++20	76 / 100	1025 ms	178704 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 {
	bool check() {
		return (n <= 5'000);
	}

	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';
			}
		}
	}
}

namespace sub6 {
	struct SegTree {
		struct Node {
			struct Position {
				int comp; // the value must be same when querying
				int pos_comp; // the value represents the order of the ships
				int idx; // the index of the ship
				Position() {};
				Position(int _comp, int _pos_comp, int _idx) : comp(_comp), pos_comp(_pos_comp), idx(_idx) {};

				bool operator<(const Position& other) const {
					if (this->comp != other.comp) return this->comp < other.comp;
					if (this->pos_comp != other.pos_comp) return this->pos_comp < other.pos_comp;
					return this->idx < other.idx;
				}
			};

			set<Position> st;
			Node() {};
		};
	
		int n_node = 0;
		vector<Node> tree;
	
		void resize(int n) { n_node = n; tree.resize((n_node << 2) + 10); }
		SegTree() {};
		SegTree(int n) { this->resize(n); }
	
		void add(int node, int l, int r, int idx, Node::Position val) {
			if (l > idx || r < idx) return;
			if (l <= idx && idx <= r) {
				// cerr << "ADD NODE: " << node << '\n'; 
				tree[node].st.insert(val);
				if (l == r) return;
			}
			int mid = (l + r) >> 1;
			add(node << 1, l, mid, idx, val);
			add(node << 1 | 1, mid + 1, r, idx, val);
		}
	
		void Add(int pos_comp, int comp, int idx) {
			return add(1, 1, n_node, pos_comp, Node::Position(comp, pos_comp, idx));
		}

		void erase(int node, int l, int r, int idx, Node::Position val) {
			if (l > idx || r < idx) return;
			if (l <= idx && idx <= r) {
				// cerr << node << ' ' << "TREE SIZE BEFORE: " << tree[node].st.size() << '\n';
				tree[node].st.erase(val);
				// cerr << node << ' ' << "TREE SIZE AFTER: " << tree[node].st.size() << '\n';
				if (l == r) return;
			}
			int mid = (l + r) >> 1;
			erase(node << 1, l, mid, idx, val);
			erase(node << 1 | 1, mid + 1, r, idx, val);
		}
	
		void Erase(int pos_comp, int comp, int idx) {
			return erase(1, 1, n_node, pos_comp, Node::Position(comp, pos_comp, idx));
		}
	
		pair<int, int> query(int node, int l, int r, int L, int R, Node::Position value) {
			if (L <= l && r <= R) {
				auto ptr = tree[node].st.lower_bound(value);
				if (ptr == tree[node].st.end() || ptr->comp != value.comp) {
					return make_pair(INF, INF);
				}
				return make_pair(ptr->pos_comp, ptr->idx);
			}
			int mid = (l + r) >> 1;
			if (R <= mid) return query(node << 1, l, mid, L, R, value);
			if (L > mid) return query(node << 1 | 1, mid + 1, r, L, R, value);
			return min(query(node << 1, l, mid, L, R, value), query(node << 1 | 1, mid + 1, r, L, R, value));
		}
	
		pair<int, int> Query(int l, int r, int value) {
			if (l > r) return make_pair(INF, INF); // arbitrary
			return query(1, 1, n_node, l, r, Node::Position(value, 0, 0));
		}
	};
	
	int fake_x[N], fake_y[N];
	vector<int> groupS[N], groupE[N];

	bool mark[N];

	void compress() {
		vector<int> Pos_x = {};
		vector<int> Pos_y = {};
		for (int i = 1; i <= n; ++ i) {
			Pos_x.push_back(ships[i - 1].x);
			Pos_y.push_back(ships[i - 1].y);
		}
		
		sort(Pos_x.begin(), Pos_x.end());
		Pos_x.resize(unique(Pos_x.begin(), Pos_x.end()) - Pos_x.begin());
	
		sort(Pos_y.begin(), Pos_y.end());
		Pos_y.resize(unique(Pos_y.begin(), Pos_y.end()) - Pos_y.begin());
	
		for (int i = 1; i <= n; ++ i) {
			fake_x[i - 1] = lower_bound(Pos_x.begin(), Pos_x.end(), ships[i - 1].x) - Pos_x.begin() + 1;
			fake_y[i - 1] = lower_bound(Pos_y.begin(), Pos_y.end(), ships[i - 1].y) - Pos_y.begin() + 1;
		}
	}
	
	void solve() {
		compress();
		for (int i = 0; i < n; ++i) {
			int dir = ships[i].dir;
			if (dir == 3) groupS[fake_y[i]].push_back(i);
			else if (dir == 2) groupE[fake_y[i]].push_back(i);
			else assert(false);
		}
		SegTree st(n);
		for (int i = 1; i <= n; ++i) {
			for (const auto& idx : groupS[i - 1]) {
				// cerr << "ADD: " << fake_x[idx] << ' ' << ships[idx].x + ships[idx].y << ' ' << idx << '\n';
				st.Add(fake_x[idx], ships[idx].x + ships[idx].y, idx);
			}
			for (const auto& idx : groupE[i]) {
				auto [pos_comp, idx_rem] = st.Query(fake_x[idx] + 1, n, ships[idx].x + ships[idx].y);
				if (idx_rem >= INF) continue;
				assert(pos_comp > fake_x[idx]);
				mark[idx_rem] = mark[idx] = true;
				// cerr << "COLLISION: " << idx + 1 << ' ' << idx_rem + 1 << '\n';
				// cerr << "REM: " << fake_x[idx_rem] << ' ' << ships[idx_rem].x + ships[idx_rem].y << ' ' << idx_rem << '\n';
				st.Erase(fake_x[idx_rem], ships[idx_rem].x + ships[idx_rem].y, idx_rem);
				// for (int node_index = 0; node_index < st.tree.size(); ++node_index) {
				// 	for (const auto& [comp, pos_comp, idx] : st.tree[node_index].st) cerr << node_index << ' ' << "VALID: " << pos_comp << ' ' << comp << ' ' << idx << '\n';
				// 	// cerr << '\n';
				// }
			}
		}
		for (int i = 0; i < n; ++i) {
			if (mark[i]) continue;
			cout << i + 1 << '\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));
	}
	if (sub5::check()) {
		sub5::solve();
		return 0;
	}
	sub6::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: 30 / 30
• Subtask 7: 0 / 24