Submission #1235751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235751		trimkus	Naval battle (CEOI24_battle)	C++20	6 / 100	3096 ms	71844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int N;
	cin >> N;
	map<char, int> mp = {{'E', 0}, {'S', 1}, {'W', 2}, {'N', 3}};
	vector<array<int, 3>> a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i][0] >> a[i][1];
		char c;
		cin >> c;
		int id = mp[c];
		a[i][2] = id;
	}
	vector<map<int, set<array<int, 2>>>> coord(4);
	for (int i = 0; i < N; ++i) {
		if (a[i][2] != 1 && a[i][2] != 2) {
			coord[a[i][2]][a[i][0] + a[i][1]].insert({a[i][0], i});
		}
	}
	priority_queue<array<int, 3>> pq;
	for (int i = 0; i < N; ++i) {
		if (a[i][2] == 1) {
			set<array<int, 2>>& c = coord[0][a[i][0] + a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.begin()) {
				--it;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		} else if (a[i][2] == 2) {
			set<array<int, 2>>& c = coord[3][a[i][0] + a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.begin()) {
				--it;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		}
	}
	for (int i = 0; i < 4; ++i) coord[i].clear();
	for (int i = 0; i < N; ++i) {
		if (a[i][2] != 3 && a[i][2] != 2) {
			coord[a[i][2]][a[i][0] - a[i][1]].insert({a[i][0], i});
		}
	}
	for (int i = 0; i < N; ++i) {
		if (a[i][2] == 3) {
			set<array<int, 2>>& c = coord[0][a[i][0] - a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.begin()) {
				--it;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		} else if (a[i][2] == 2) {
			set<array<int, 2>>& c = coord[1][a[i][0] - a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.begin()) {
				--it;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		}
	}
	for (int i = 0; i < 4; ++i) coord[i].clear();
	for (int i = 0; i < N; ++i) {
		if (a[i][2] != 3 && a[i][2] != 2) {
			if (a[i][2] == 0) coord[a[i][2]][a[i][1]].insert({a[i][0], i});
			else coord[a[i][2]][a[i][0]].insert({a[i][1], i});
		}
	}
	for (int i = 0; i < N; ++i) {
		if (a[i][2] == 3) {
			set<array<int, 2>>& c = coord[1][a[i][0]];
			auto it = c.upper_bound({a[i][1], -1});
			if (it != c.end()) {
				int tim =  -a[i][1] + (*it)[0];
				assert(tim > 0 && tim % 2 == 0);
				tim /= 2;
				pq.push({-tim, i, (*it)[1]});
			}
		} else if (a[i][2] == 2) {
			set<array<int, 2>>& c = coord[1][a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.begin()) {
				--it;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				assert(tim % 2 == 0);
				tim /= 2;
				pq.push({-tim, i, (*it)[1]});
			}
		}
	}
	for (int i = 0; i < 4; ++i) coord[i].clear();
	vector<map<int, set<array<int, 2>>>> pos(4), neg(4), line(4);
	for (int i = 0; i < N; ++i) {
		if (a[i][2] % 2 == 0) line[a[i][2]][a[i][1]].insert({a[i][0], i});
		else line[a[i][2]][a[i][0]].insert({a[i][1], i});
		pos[a[i][2]][a[i][0] + a[i][1]].insert({a[i][0], i});
		neg[a[i][2]][a[i][0] - a[i][1]].insert({a[i][0], i});
	}
	auto del = [&](int i) -> void {
		if (a[i][2] % 2 == 0) line[a[i][2]][a[i][1]].erase({a[i][0], i});
		else line[a[i][2]][a[i][0]].erase({a[i][1], i});
		pos[a[i][2]][a[i][0] + a[i][1]].erase({a[i][0], i});
		neg[a[i][2]][a[i][0] - a[i][1]].erase({a[i][0], i});
	};
	auto ins = [&](int i) -> void {
		if (a[i][2] == 0) {
			auto& c = line[2][a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.end()) {
				int tim = -a[i][0] + (*it)[0];
				assert(tim > 0 && tim % 2 == 0);
				tim /= 2;
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c1 = pos[1][a[i][0] + a[i][1]];
			auto it1 = c1.upper_bound({a[i][0], -1});
			if (it1 != c1.end()) {
				int tim = -a[i][0] + (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c2 = neg[3][a[i][0] - a[i][1]];
			auto it2 = c2.upper_bound({a[i][0], -1});
			if (it2 != c2.end()) {
				int tim = -a[i][0] + (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		} else if (a[i][2] == 1) {
			auto& c = line[3][a[i][0]];
			auto it = c.upper_bound({a[i][1], -1});
			if (it != c.begin()) {
				it--;
				int tim = a[i][1] - (*it)[0];
				assert(tim > 0 && tim % 2 == 0);
				tim /= 2;
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c1 = pos[0][a[i][0] + a[i][1]];
			auto it1 = c1.upper_bound({a[i][0], -1});
			if (it1 != c1.begin()) {
				it1--;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c2 = neg[2][a[i][0] - a[i][1]];
			auto it2 = c2.upper_bound({a[i][0], -1});
			if (it2 != c2.end()) {
				int tim = -a[i][0] + (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		} else if (a[i][2] == 2) {
			auto& c = line[0][a[i][1]];
			auto it = c.upper_bound({a[i][0], -1});
			if (it != c.begin()) {
				it--;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0 && tim % 2 == 0);
				tim /= 2;
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c1 = pos[3][a[i][0] + a[i][1]];
			auto it1 = c1.upper_bound({a[i][0], -1});
			if (it1 != c1.begin()) {
				it1--;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c2 = neg[1][a[i][0] - a[i][1]];
			auto it2 = c2.upper_bound({a[i][0], -1});
			if (it2 != c2.begin()) {
				it2--;
				int tim = a[i][0] - (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		} else {
			auto& c = line[1][a[i][0]];
			auto it = c.upper_bound({a[i][1], -1});
			if (it != c.end()) {
				int tim = -a[i][1] + (*it)[0];
				assert(tim > 0 && tim % 2 == 0);
				tim /= 2;
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c1 = pos[2][a[i][0] + a[i][1]];
			auto it1 = c1.upper_bound({a[i][0], -1});
			if (it1 != c1.end()) {
				int tim = -a[i][0] + (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
			auto& c2 = neg[0][a[i][0] - a[i][1]];
			auto it2 = c2.upper_bound({a[i][0], -1});
			if (it2 != c2.begin()) {
				it2--;
				int tim = -a[i][0] + (*it)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it)[1]});
			}
		}
	};
	vector<int> vis(N);
	int timer = 1;
	// auto nq = pq;
	// while (nq.size()) {
	// 	cout << -nq.top()[0] << " " << nq.top()[1] + 1 << " " << nq.top()[2] + 1 << "\n";
	// 	nq.pop();
	// }
	while (pq.size()) {
		int d = -pq.top()[0];
		vector<int> recalc;
		while (pq.size() && -pq.top()[0] == d) {
			int i = pq.top()[1];
			int j = pq.top()[2];
			pq.pop();
			// cout << d << " = " << i + 1 << " " << j + 1 << "\n";
			if (vis[i] > 0) {
				if (vis[i] == timer) {
					if (vis[j] == 0) {
						del(j);
						vis[j] = timer;
					}
				} else if (vis[j] == 0) {
					recalc.push_back(j);
				}
			}
			if (vis[j] > 0) {
				if (vis[j] == timer) {
					if (vis[i] == 0) {
						del(i);
						vis[i] = timer;
					}
				} else if (vis[i] == 0) {
					recalc.push_back(i);
				}
			}
			if (vis[i] == 0 && vis[j] == 0) {
				vis[i] = vis[j] = timer;
				del(i);
				del(j);
			}
		}
		for (auto& u : recalc) {
			ins(u);
		}
		timer += 1;
	}
	for (int i = 0; i < N; ++i) {
		if (vis[i] == 0) {
			cout << i + 1 << "\n";
		}
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 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