Submission #1235773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235773		trimkus	Naval battle (CEOI24_battle)	C++20	36 / 100	1412 ms	88532 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) assert(line[a[i][2]][a[i][1]].erase({a[i][0], i}));
		else assert(line[a[i][2]][a[i][0]].erase({a[i][1], i}));
		assert(pos[a[i][2]][a[i][0] + a[i][1]].erase({a[i][0], i}));
		assert(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] + (*it1)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it1)[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] + (*it2)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it2)[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] - (*it1)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it1)[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] + (*it2)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it2)[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] - (*it1)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it1)[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] - (*it2)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it2)[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] + (*it1)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it1)[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] + (*it2)[0];
				assert(tim > 0);
				pq.push({-tim, i, (*it2)[1]});
			}
		}
	};
	int timer = 1;
	// auto nq = pq;
	// while (nq.size()) {
	// 	cout << -nq.top()[0] << " " << nq.top()[1] + 1 << " " << nq.top()[2] + 1 << "\n";
	// 	nq.pop();
	// }
	// ofstream cout("out.txt");
	unordered_set<int> deleted;
	while (pq.size()) {
		int d = -pq.top()[0];
		vector<int> recalc;
		vector<int> todel;
		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 << " = " << deleted.count(i) << " " << deleted.count(j) << "\n";
			// if (i + 1 == 70 && j + 1 == 1) break;
			// if (deleted.count(i) || deleted.count(j)) continue;
			if (deleted.count(i) && !deleted.count(j)) recalc.push_back(j);
			else if (deleted.count(j) && !deleted.count(i)) recalc.push_back(i);
			else if (!deleted.count(j) && !deleted.count(i)) {
				todel.push_back(i);
				todel.push_back(j);
			}
		}
		sort(begin(todel), end(todel));
		todel.erase(unique(begin(todel), end(todel)), end(todel));
		for (auto& u : todel) {
			del(u);
			deleted.insert(u);
		}
		// cout << pq.size() << " -> ";
		for (auto& u : recalc) {
			ins(u);
		}
		// cout << pq.size() << "\n";
		// cout << "end\n";
	}
	for (int i = 0; i < N; ++i) {
		if (!deleted.count(i)) {
			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: 30 / 30
• Subtask 7: 0 / 24