Submission #1236073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236073		trimkus	Naval battle (CEOI24_battle)	C++20	6 / 100	3098 ms	104384 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
signed 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;
	}
	priority_queue<array<int, 3>> pq;
	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 calc = [&](int i, int j) -> int {
		int x1 = a[i][0], y1 = a[i][1];
		int x2 = a[j][0], y2 = a[j][1];
		cerr << i << " " << j << " = ";
		cerr << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
		int sum = llabs(x1 - x2) + llabs(y1 - y2);
// 		cout << sum << "\n";
		assert(sum % 2 == 0);
		assert(sum > 0);
		return sum / 2;
	};
	set<int> deleted;
	vector<char> C = {'E', 'S', 'W', 'N'};
	set<string> st;
	for (char c : C) {
		for (char ci : C) {
			if (c == ci) continue;
			string s = ""; s += c; s += ci;
			st.insert(s);
		}
	}
	auto dbg = [&](int i, int j) -> void {
		int x1 = a[i][0], y1 = a[i][1], x2 = a[j][0], y2 = a[j][1];
		string s = ""; s += C[a[i][2]]; s += C[a[j][2]];
		if (!st.count(s)) {
			cerr << "Trying to match an impossible case: " << s << "\n";
			assert(false);
		}
		if (abs(a[i][2] - a[j][2]) % 2 == 0) {
			if (a[i][2] == 0 || a[j][2] == 0) {
				if (y1 != y2) {
					cerr << "Wrong matching for a line " << i + 1 << " " << j + 1 << "!\n";
					assert(false);
				}
			} else if (a[i][2] == 1 || a[j][2] == 1) {
				if (x1 != x2) {
					cerr << "Wrong matching for a line " << i + 1 << " " << j + 1 << "!\n";
					assert(false);
				}
			}
			return;
		}
		int k1 = abs(x1 - x2);
		int k2 = abs(y1 - y2);
		cerr << k1 << " " << k2 << "\n";
		if (k1 != k2) {
			cerr << "Incorrect matching at " << i + 1 << " " << j + 1 << "!\n";
			assert(false);
		}
	};
	cerr << "neg:\n";
	for (int i = 0; i < 4; ++i) {
		cerr << i << ":\n";
		for (auto u : neg[i]) {
			cerr << u.first << " = \n";
			for (auto v : u.second) {
				cerr << "( " << a[v[1]][0] << " , " << a[v[1]][1] << " )\n";
			}
			cerr << "\n";
		}
	}
	cerr << "pos:\n";
	for (int i = 0; i < 4; ++i) {
		cerr << i << ":\n";
		for (auto u : pos[i]) {
			cerr << u.first << " = \n";
			for (auto v : u.second) {
				cerr << "( " << a[v[1]][0] << " , " << a[v[1]][1] << " )\n";
			}
			cerr << "\n";
		}
	}
	cerr << "line: \n";
	for (int i = 0; i < 4; ++i) {
		cerr << i << ":\n";
		for (auto u : line[i]) {
			cerr << u.first << " = \n";
			for (auto v : u.second) {
				cerr << "( " << a[v[1]][0] << " , " << a[v[1]][1] << " )\n";
			}
			cerr << "\n";
		}
	}
	auto pushit = [&](auto& M, int x, int k, bool up, int i, string name_of_bucket) -> void {
		cerr << "Lookup in " << name_of_bucket 
		<< " for key="<< k 
		<< " → found? " << (M.count(k) ? "true!" : "false...") << "\n";
		if (!M.count(k)) return;
		set<array<int, 2>>& v = M[k];
		auto it = v.lower_bound({x, -1});
		if (up) {
			if (it == end(v)) return;
			if ((*it)[0] == x) {
				++it;
				if (it == end(v)) return;
			}
		} else {
			if ((*it)[0] == x) {
				if (it == begin(v)) return;
				it--;
			}
		}
		if (it == end(v)) return;
		int j = (*it)[1];
		assert(j < N);
		int t = calc(i, j);
		assert(!deleted.count(j));
		dbg(i, j);
		pq.push({-t, i, j});
	};
	auto add = [&](int i) -> void {
		int x = a[i][0];
		int y = a[i][1];
		if (a[i][2] == 0) {
			pushit(neg[3], x, x - y, true, i, "neg 3");
			pushit(pos[1], x, x + y, true, i, "pos 1");
			pushit(line[2], x, y, true, i, "line 2");
		}
		if (a[i][2] == 2) {
			pushit(neg[1], x, x - y, false, i, "neg 1");
			pushit(pos[3], x, x + y, false, i, "pos 3");
			pushit(line[0], x, y, false, i, "line 0");
		}
		if (a[i][2] == 1) {
			pushit(neg[2], x, x - y, false, i, "neg 2");
			pushit(pos[0], x, x + y, true, i, "pos 0");
			pushit(line[3], y, x, true, i, "line 3");
		}
		if (a[i][2] == 3) {
			pushit(neg[0], x, x - y, true, i, "neg 2");
			pushit(pos[2], x, x + y, false, i, "pos 0");
			pushit(line[1], y, x, false, i, "line 1");
		}
	};
	for (int i = 0; i < N; ++i) {
		// cerr << i << "\n";
		add(i);
	}
	vector<int> todelete, tocalc;
	auto get_unique = [&](vector<int>& v) -> void {
		sort(begin(v), end(v));
		v.erase(unique(begin(v), end(v)), end(v));
	};
	auto rem = [&](int i) -> void {
		// line[a[i][2]][a[i][1]].insert({a[i][0], i});
		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}));
	};
	
	// cerr << pq.size() << endl;
	while (pq.size()) {
		int d = -pq.top()[0];
		while (pq.size() && d == -pq.top()[0]) {
			int i = pq.top()[1];
			int j = pq.top()[2];
			pq.pop();
			int fi = deleted.count(i);
			int fj = deleted.count(j);
			cerr << i + 1 << " " << j  + 1 << " " << fi << " " << fj << endl;
			if (fi && fj) continue;
			if (fi && !fj) tocalc.push_back(j);
			else if (!fi && fj) tocalc.push_back(i);
			else {
				assert(!fi && !fj);
				todelete.push_back(i);
				todelete.push_back(j);
			}
		}
		get_unique(todelete);
		get_unique(tocalc);
		while (todelete.size()) {
			int v = todelete.back();
			todelete.pop_back();
			// cout << v << " ";
			assert(!deleted.count(v));
			rem(v);
			deleted.insert(v);
		}
		// cout << "\n";
		while (tocalc.size()) {
			int v = tocalc.back();
			tocalc.pop_back();
			add(v);
		}
	}
// 	cout << N << "\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: 0 / 30
• Subtask 7: 0 / 24