Submission #1044055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044055		alex_2008	Naval battle (CEOI24_battle)	C++14	76 / 100	375 ms	148464 KiB

Main

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int a[N], x[N], y[N];
char dir[N];
bool used[N];
int ind[N];
bool cmp(int a, int b) {
	if (x[a] != x[b]) return x[a] > x[b];
	if (y[a] != y[b]) return y[b] > y[a];
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i] >> dir[i];
	}
	if (n <= 5000) {
		priority_queue <pair<int, pair<int, int>>> Q;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (dir[i] == 'N') {
					if (dir[j] == 'W') {
						if (x[j] > x[i] && (x[j] - x[i]) == (y[i] - y[j])) {
							Q.push({ -(x[j] - x[i]), { i, j } });
						}
					}
					else if (dir[j] == 'E') {
						if (x[j] < x[i] && (x[i] - x[j]) == (y[i] - y[j])) {
							Q.push({ -(x[i] - x[j]), { i, j } });
						}
					}
					else if (dir[j] == 'S') {
						if (x[i] == x[j] && y[i] > y[j]) {
							Q.push({ -(y[i] - y[j]) / 2, { i, j } });
						}
					}
					continue;
				}
				if (dir[i] == 'S') {
					if (dir[j] == 'W') {
						if (x[j] > x[i] && (x[j] - x[i]) == (y[j] - y[i])) {
							Q.push({ -(x[j] - x[i]), { i, j } });
						}
					}
					else if (dir[j] == 'E') {
						if (x[j] < x[i] && (x[i] - x[j]) == (y[j] - y[i])) {
							Q.push({ -(x[i] - x[j]), { i, j } });
						}
					}
					else if (dir[j] == 'N') {
						if (x[i] == x[j] && y[j] > y[i]) {
							Q.push({ -(y[j] - y[i]) / 2, { i, j } });
						}
					}
					continue;
				}
				if (dir[i] == 'E') {
					if (dir[j] == 'N') {
						if (x[j] > x[i] && (x[j] - x[i]) == (y[j] - y[i])) {
							Q.push({ -(x[j] - x[i]), { i, j } });
						}
					}
					else if (dir[j] == 'S') {
						if (x[j] > x[i] && (x[j] - x[i]) == (y[i] - y[j])) {
							Q.push({ -(x[j] - x[i]), { i, j } });
						}
					}
					else if (dir[j] == 'W') {
						if (y[i] == y[j] && x[i] < x[j]) {
							Q.push({ -(x[j] - x[i]) / 2, { i, j } });
						}
					}
					continue;
				}
				if (dir[i] == 'W') {
					if (dir[j] == 'N') {
						if (x[i] > x[j] && (x[i] - x[j]) == (y[j] - y[i])) {
							Q.push({ -(x[i] - x[j]), { i, j } });
						}
					}
					else if (dir[j] == 'S') {
						if (x[i] > x[j] && (x[i] - x[j]) == (y[i] - y[j])) {
							Q.push({ -(x[i] - x[j]), { i, j } });
						}
					}
					else if (dir[j] == 'E') {
						if (y[i] == y[j] && x[i] > x[j]) {
							Q.push({ -(x[i] - x[j]) / 2, { i, j } });
						}
					}
					continue;
				}
			}
		}
		while (1) {
			if (Q.empty()) break;
			pair <int, pair<int, int>> t = Q.top();
			vector <int> v;
			while (!Q.empty() && Q.top().first == t.first) {
				int x = Q.top().second.first, y = Q.top().second.second;
				if (!used[x] && !used[y]) {
					v.push_back(x);
					v.push_back(y);
				}
				Q.pop();
			}
			for (auto it : v) {
				used[it] = true;
			}
		}
		for (int i = 1; i <= n; i++) {
			if (!used[i]) {
				cout << i << "\n";
			}
		}
		return 0;
	}
	map <int, stack<int>> mp;
	for (int i = 1; i <= n; i++) {
		ind[i] = i;
	}
	sort(ind + 1, ind + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		if (dir[ind[i]] == 'S') {
			mp[x[ind[i]] + y[ind[i]]].push(ind[i]);
		}
		else {
			if (mp[x[ind[i]] + y[ind[i]]].empty()) {
				cout << ind[i] << "\n";
			}
			else mp[x[ind[i]] + y[ind[i]]].pop();
		}
	}
	for (auto it : mp) {
		while (!it.second.empty()) {
			cout << it.second.top() << "\n";
			it.second.pop();
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'bool cmp(int, int)':
Main.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

• 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