Submission #1220263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220263		MateiKing80	Naval battle (CEOI24_battle)	C++20	46 / 100	2660 ms	1114112 KiB

Main

#include <bits/stdc++.h> 

using namespace std;

using ll = long long;
#define int ll

signed main() {
	int n;
	cin >> n;
	vector<array<int, 2>> a(n);
	vector<char> t(n);
	for (int i = 0; i < n; i ++) {
		int x, y;
		char dir;
		cin >> x >> y >> dir;
		a[i] = {x, y};
		t[i] = dir;
	}
	auto time = [&](int i, int j) {
		int ans = 1e18;
		if (t[i] == 'N' && t[j] == 'W' && a[i][0] + a[i][1] == a[j][0] + a[j][1]) 
			ans = a[j][0] - a[i][0];
		if (t[i] == 'E' && t[j] == 'S' && a[i][0] + a[i][1] == a[j][0] + a[j][1]) 
			ans = a[j][0] - a[i][0];
		if (t[i] == 'E' && t[j] == 'N' && a[i][0] - a[i][1] == a[j][0] - a[j][1]) 
			ans = a[j][0] - a[i][0];
		if (t[i] == 'S' && t[j] == 'W' && a[i][0] - a[i][1] == a[j][0] - a[j][1]) 
			ans = a[j][0] - a[i][0];
		if (t[i] == 'E' && t[j] == 'W' && a[i][1] == a[j][1]) 
			ans = (a[j][0] - a[i][0]) / 2;
		if (t[i] == 'N' && t[j] == 'S' && a[i][0] == a[j][0]) 
			ans = (a[i][1] - a[j][1]) / 2;
		if (ans < 0) 
			ans = 1e18;
		return ans;
	};
	vector<array<int, 3>> v;
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < n; j ++)
				if (time(i, j) != 1e18)
					v.push_back({time(i, j), i, j});
	sort(v.begin(), v.end());
	vector<int> vis(n);
	for (auto [val, i, j] : v) {
		if (val < 0) 
			continue;
		if (!vis[i] && !vis[j]) {
			vis[i] = val;
			vis[j] = val;
		} else if (!vis[i] && val == vis[j]) {
			vis[i] = val;
		} else if (!vis[j] && val == vis[i]) {
			vis[j] = val;
		}
	}
	vector<int> ans;
	for (int i = 0; i < n; i ++) 
		if (!vis[i]) 
			ans.push_back(i);
	for (int i : ans) 
		cout << i + 1 << '\n';
}

• 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