Submission #1044216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044216		Tsovak	Naval battle (CEOI24_battle)	C++17	76 / 100	475 ms	44816 KiB

Main

// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout << fixed << setprecision(x);
	return;
}

ll gcd0(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

ll lcm0(ll a, ll b)
{
	return a / gcd0(a, b) * b;
}

bool is_prime(ll a)
{
	if (a == 1) return false;
	for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false;
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrtl(ld(a)));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrtl(ld(a)));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}

ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans *= ll(i);
	return ans;
}

ll factorial_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod;
	return ans;
}

// -------------------- Solution -------------------- //

const pr<int, pr<int, int>> null = mpr(-1, mpr(-1, -1));

struct ship
{
	int x, y;
	char d;
};

const int N = 200005;
ship a[N];
bool used[N];
int n;

vector<pr<pr<int, pr<int, int>>, pr<int, int>>> v;
vector<pr<int, int>> vv;

pr<int, pr<int, int>> col(ship x, ship y)
{
	if (x.d == y.d) return null;

	if (x.x == y.x) {
		if (x.d == 'E' || x.d == 'W' || y.d == 'E' || y.d == 'W') return null;

		if (x.y > y.y) swap(x, y);

		if (x.d == 'S' && y.d == 'N') return mpr((y.y - x.y) / 2, mpr(x.x, (x.y + y.y) / 2));

		return null;
	}

	if (x.y == y.y) {
		if (x.d == 'N' || x.d == 'S' || y.d == 'N' || y.d == 'S') return null;

		if (x.x > y.x) swap(x, y);

		if (x.d == 'E' && y.d == 'W') return mpr((y.x - x.x) / 2, mpr((x.x + y.x) / 2, x.y));

		return null;
	}

	if (x.x - x.y == y.x - y.y) {
		if (x.x > y.x) swap(x, y);

		if (x.d == 'E' && y.d == 'N') return mpr(y.x - x.x, mpr(y.x, x.y));

		if (x.d == 'S' && y.d == 'W') return mpr(y.x - x.x, mpr(x.x, y.y));

		return null;
	}

	if (x.x + x.y == y.x + y.y) {
		if (x.x > y.x) swap(x, y);

		if (x.d == 'N' && y.d == 'W') return mpr(y.x - x.x, mpr(x.x, y.y));

		if (x.d == 'E' && y.d == 'S') return mpr(y.x - x.x, mpr(y.x, x.y));

		return null;
	}

	return null;
}

vector<pr<int, int>> vb, vc;

void solve()
{
	int i, j;

	cin >> n;

	for (i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].d;

	if (n <= 5000) {
		pr<int, pr<int, int>> e;

		for (i = 1; i < n; i++) {
			for (j = i + 1; j <= n; j++) {
				e = col(a[i], a[j]);

				if (e == null) continue;

				v.pb(mpr(e, mpr(i, j)));
			}
		}

		sort(all(v));

		int ind = 0;

		while (ind < sz(v)) {
			clr(vv);

			e = v[ind].ff;
			vv.pb(v[ind].ss);

			for (i = ind + 1; i < sz(v); i++) {
				if (v[i].ff != e) break;

				if (used[v[i].ss.ff] || used[v[i].ss.ss]) continue;

				vv.pb(v[i].ss);
			}

			for (i = 0; i < sz(vv); i++) used[vv[i].ff] = used[vv[i].ss] = true;

			while (i < sz(v) && (used[v[i].ss.ff] || used[v[i].ss.ss])) i++;

			ind = i;
		}

		for (i = 1; i <= n; i++) if (!used[i]) cout << i << "\n";

		return;
	}


	for (i = 1; i <= n; i++) vb.pb(mpr(a[i].x + a[i].y, i));

	sort(all(vb));

	int ind = 0;

	stack<int> st;

	while (ind < sz(vb)) {
		clr(vc);

		for (i = ind; i < sz(vb); i++) {
			if (vb[i].ff != vb[ind].ff) break;
			vc.pb(mpr(a[vb[i].ss].x, vb[i].ss));
		}

		ind = i;

		sort(all(vc));


		for (i = 0; i < sz(vc); i++) {
			if (a[vc[i].ss].d == 'S') {
				if (!st.empty() && a[st.top()].d == 'E') {
					used[vc[i].ss] = used[st.top()] = true;
					st.pop();
				}
				else st.push(vc[i].ss);
			}
			else st.push(vc[i].ss);
		}

		while (!st.empty()) st.pop();
	}

	for (i = 1; i <= n; i++) if (!used[i]) cout << i << "\n";

	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

• 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