Submission #1044275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044275		Tsovak	Naval battle (CEOI24_battle)	C++17	6 / 100	3026 ms	65216 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;

	vector<int> vo;
};

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;
}

map<int, vector<pr<int, int>>> mpx, mpy, mp11, mp12, mp21, mp22;

void init()
{
	int i, j;

	for (i = 1; i <= n; i++) {
		if (a[i].d == 'N') {
			mpx[a[i].x].pb(mpr(a[i].y, i));
			mp11[a[i].x - a[i].y].pb(mpr(a[i].x, i));
			mp21[a[i].x + a[i].y].pb(mpr(a[i].x, i));
		}
		else if (a[i].d == 'S') {
			mpx[a[i].x].pb(mpr(a[i].y, i));
			mp12[a[i].x - a[i].y].pb(mpr(a[i].x, i));
			mp22[a[i].x + a[i].y].pb(mpr(a[i].x, i));
		}
		else if (a[i].d == 'E') {
			mpy[a[i].y].pb(mpr(a[i].x, i));
			mp11[a[i].x - a[i].y].pb(mpr(a[i].x, i));
			mp22[a[i].x + a[i].y].pb(mpr(a[i].x, i));
		}
		else {
			mpy[a[i].y].pb(mpr(a[i].x, i));
			mp12[a[i].x - a[i].y].pb(mpr(a[i].x, i));
			mp21[a[i].x + a[i].y].pb(mpr(a[i].x, i));
		}
	}

	return;
}

set<pr<pr<int, pr<int, int>>, pr<int, int>>> st;

void solve()
{
	int i, j;

	cin >> n;

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

	init();


	for (auto p : mpx) sort(all(mpx[p.ff]));
	for (auto p : mpy) sort(all(mpy[p.ff]));
	for (auto p : mp11) sort(all(mp11[p.ff]));
	for (auto p : mp12) sort(all(mp12[p.ff]));
	for (auto p : mp21) sort(all(mp21[p.ff]));
	for (auto p : mp22) sort(all(mp22[p.ff]));


	stack<int> st;

	for (auto p : mpx) {
		while (!st.empty()) st.pop();

		for (i = 0; i < sz(p.ss); i++) {
			if (a[p.ss[i].ss].d == 'N' && !st.empty() && a[st.top()].d == 'S') {
				a[p.ss[i].ss].vo.pb(st.top());
				a[st.top()].vo.pb(p.ss[i].ss);

				st.pop();
			}
			else st.push(p.ss[i].ss);
		}
	}

	for (auto p : mpy) {
		while (!st.empty()) st.pop();

		for (i = 0; i < sz(p.ss); i++) {
			if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'E') {
				a[p.ss[i].ss].vo.pb(st.top());
				a[st.top()].vo.pb(p.ss[i].ss);

				st.pop();
			}
			else st.push(p.ss[i].ss);
		}
	}

	for (auto p : mp11) {
		while (!st.empty()) st.pop();

		for (i = 0; i < sz(p.ss); i++) {
			if (a[p.ss[i].ss].d == 'N' && !st.empty() && a[st.top()].d == 'E') {
				a[p.ss[i].ss].vo.pb(st.top());
				a[st.top()].vo.pb(p.ss[i].ss);

				st.pop();
			}
			else st.push(p.ss[i].ss);
		}
	}

	for (auto p : mp12) {
		while (!st.empty()) st.pop();

		for (i = 0; i < sz(p.ss); i++) {
			if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'S') {
				a[p.ss[i].ss].vo.pb(st.top());
				a[st.top()].vo.pb(p.ss[i].ss);

				st.pop();
			}
			else st.push(p.ss[i].ss);
		}
	}

	for (auto p : mp21) {
		while (!st.empty()) st.pop();

		for (i = 0; i < sz(p.ss); i++) {
			if (a[p.ss[i].ss].d == 'W' && !st.empty() && a[st.top()].d == 'N') {
				a[p.ss[i].ss].vo.pb(st.top());
				a[st.top()].vo.pb(p.ss[i].ss);

				st.pop();
			}
			else st.push(p.ss[i].ss);
		}
	}

	for (auto p : mp22) {
		while (!st.empty()) st.pop();

		for (i = 0; i < sz(p.ss); i++) {
			if (a[p.ss[i].ss].d == 'S' && !st.empty() && a[st.top()].d == 'E') {
				a[p.ss[i].ss].vo.pb(st.top());
				a[st.top()].vo.pb(p.ss[i].ss);

				st.pop();
			}
			else st.push(p.ss[i].ss);
		}
	}



	pr<int, pr<int, int>> e;

	for (i = 1; i < n; i++) {
		for (j = 0; j < sz(a[i].vo); j++) {
			if (a[i].vo[j] < i) continue;

			e = col(a[i], a[a[i].vo[j]]);

			if (e == null) assert(false);

			v.pb(mpr(e, mpr(i, a[i].vo[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;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

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

	return 0;
}

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

Compilation message (stderr)

Main.cpp: In function 'void init()':
Main.cpp:253:9: warning: unused variable 'j' [-Wunused-variable]
  253 |  int i, j;
      |         ^

• 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