Submission #1204331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204331		NK_	Naval battle (CEOI24_battle)	C++20	6 / 100	2871 ms	1114112 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair

using ll = long long;
using pl = pair<ll, ll>;
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vi = V<int>;
using vl = V<ll>;
using vpl = V<pl>;

const int INF = 1e9 + 10;

struct T {
	array<int, 3> ans = {INF, -1, -1}; // time of crash
	int l = INF, lx = -1; // ship coming from left
	int r = -INF, rx = -1; // ship coming from right
};


struct Seg {
	T ID; 
	V<T> seg; int n; T cmb(T a, T b) {
		T c; c.ans = min(a.ans, b.ans);
		c.l = b.l, c.lx = b.lx;
		c.r = a.r, c.rx = a.rx;
		c.ans = min(a.ans, b.ans);
		if (b.r - a.l < c.ans[0]) c.ans = {b.r - a.l, a.lx, b.rx};
		return c;
	}

	void init(int _n) {
		for(n = 1; n < _n;) n *= 2;
		seg.assign(2 * n, ID);
	}

	void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); }

	void upd(int p, T x) {
		seg[p += n] = x;
		for(p /= 2; p; p /= 2) pull(p);
	}

	T qry(int l, int r) {
		T ra, rb;
		for(l += n, r += n + 1; l < r; l /= 2, r /= 2) {
			if (l & 1) ra = cmb(ra, seg[l++]);
			if (r & 1) rb = cmb(seg[--r], rb);
		}
		return cmb(ra, rb);
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vi X(N), Y(N); V<char> D(N);
	for(int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i] >> D[i];
	}

	// unordered_map<int, vi> SN, EW, EN, ES, NW, SW;
	// unordered_map<int, Seg> SNX, EWX, ENX, ESX, NWX, SWX;

	// V<vi> idx(N);
	// for(int i = 0; i < N; i++) {
	// 	if (D[i] == 'N') {
	// 		idx[i].pb(sz(SN[X[i]])); SN[X[i]].pb(i); 
	// 		idx[i].pb(sz(NW[X[i] + Y[i]])); NW[X[i] + Y[i]].pb(i);
	// 		idx[i].pb(sz(EN[X[i] - Y[i]])); EN[X[i] - Y[i]].pb(i);
	// 	}

	// 	if (D[i] == 'S') {
	// 		idx[i].pb(sz(SN[X[i]])); SN[X[i]].pb(i); 
	// 		idx[i].pb(sz(ES[X[i] + Y[i]])); ES[X[i] + Y[i]].pb(i);
	// 		idx[i].pb(sz(SW[X[i] - Y[i]])); SW[X[i] - Y[i]].pb(i);
	// 	}

	// 	if (D[i] == 'W') {
	// 		idx[i].pb(sz(EW[Y[i]])); EW[Y[i]].pb(i); 
	// 		idx[i].pb(sz(NW[X[i] + Y[i]])); NW[X[i] + Y[i]].pb(i);
	// 		idx[i].pb(sz(SW[X[i] - Y[i]])); SW[X[i] - Y[i]].pb(i);
	// 	}

	// 	if (D[i] == 'E') {
	// 		idx[i].pb(sz(EW[Y[i]])); EW[Y[i]].pb(i);
	// 		idx[i].pb(sz(ES[X[i] + Y[i]])); ES[X[i] + Y[i]].pb(i);
	// 		idx[i].pb(sz(EN[X[i] - Y[i]])); EN[X[i] - Y[i]].pb(i);
	// 	}
	// }

	V<array<int, 3>> E;
	string ord = "SWNE";
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			if (D[i] == D[j]) continue;

			if (D[i] == 'S' && D[j] == 'N') {
				if (X[i] == X[j]) {
					int t = abs(Y[i] - Y[j]);
					E.pb({t / 2, i, j});
				}
			} 

			if (D[i] == 'E' && D[j] == 'W') {
				if (Y[i] == Y[j]) {
					int t = abs(X[i] - X[j]);
					E.pb({t / 2, i, j});
				}
			}


			if (D[i] == 'S' && D[j] == 'W') {
				if (X[i] - Y[i] == X[j] - Y[j]) {
					int t = abs(X[i] - X[j]);
					E.pb({t, i, j});
				}
			}

			if (D[i] == 'N' && D[j] == 'E') {
				if (X[i] - Y[i] == X[j] - Y[j]) {
					int t = abs(X[i] - X[j]);
					E.pb({t, i, j});
				}
			}

			if (D[i] == 'N' && D[j] == 'W') {
				if (X[i] + Y[i] == X[j] + Y[j]) {
					int t = abs(X[i] - X[j]);
					E.pb({t, i, j});
				}
			}

			if (D[i] == 'S' && D[j] == 'E') {
				if (X[i] + Y[i] == X[j] + Y[j]) {
					int t = abs(X[i] - X[j]);
					E.pb({t, i, j});
				}
			}
		}
	}	

	sort(begin(E), end(E));
	vi dead(N, 0);
	for(int i = 0; i < sz(E); i++) {
		int j = i; vi upd;
		while(j < sz(E) && E[i][0] == E[j][0]) {
			auto [t, x, y] = E[j];
			// cout << t << " -> " << x << " " << y << endl;
			if (!dead[x] && !dead[y]) {
				upd.pb(x); upd.pb(y);
			}
			j++;
		}

		i = j - 1;

		for(auto& x : upd) dead[x] = 1;
	}

	for(int i = 0; i < N; i++) if (!dead[i]) cout << i + 1 << nl;

	exit(0-0);
}

// Breathe In, Breathe Out
	

• 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