Submission #1042587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042587		Tob	Naval battle (CEOI24_battle)	C++14	100 / 100	1289 ms	199232 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 2e5 + 7;
const ll inf = 1e18;

int n;
int ty[N], res[N];
pii po[N][6];
int con[4][4];
pii co[N];

vector <int> wh[4];

map <ll, set <pii> > s[6];
set <pair <ll, pii> > m;

ll dis(int x, int y) {return abs(co[x].F-co[y].F)+abs(co[x].S-co[y].S);}
void rem(int x, ll y, int o) {
	int a, b;
	auto p = ++s[o][y].find({po[x][o].F, x});
	b = p -> S;
	--p; --p; a = p -> S;
	if (b != -1 && con[ty[x]][ty[b]]) m.erase({dis(x, b), {x, b}});
	if (a != -1 && con[ty[a]][ty[x]]) m.erase({dis(a, x), {a, x}});
	s[o][y].erase(++p);
	if (a != -1 && b != -1 && con[ty[a]][ty[b]]) m.insert({dis(a, b), {a, b}});
}

int main () {
	FIO;
	cin >> n;
	
	con[0][2] = 1;
	con[1][3] = 1;
	con[0][1] = 1;
	con[1][2] = 1;
	con[3][2] = 1;
	con[0][3] = 1;
	
	wh[0] = {0, 2, 5};
	wh[1] = {1, 2, 3};
	wh[2] = {0, 4, 3};
	wh[3] = {1, 4, 5};
	
	for (int i = 0; i < n; i++) {
		char cc; cin >> co[i].S >> co[i].F >> cc;
		if (cc == 'S') ty[i] = 1;
		else if (cc == 'W') ty[i] = 2;
		else if (cc == 'N') ty[i] = 3;
		if (ty[i]%2 == 0) po[i][0] = {co[i].S, co[i].F};
		else po[i][1] = {co[i].F, co[i].S};
		po[i][wh[ty[i]][1]] = {co[i].S-co[i].F, co[i].F+co[i].S};
		po[i][wh[ty[i]][2]] = {co[i].F+co[i].S, co[i].S-co[i].F};
		for (int j = 0; j < 3; j++) {
			int di = wh[ty[i]][j];
			s[di][po[i][di].S].insert({po[i][di].F, i});
		}
	}
	
	for (int i = 0; i < 6; i++) {
		vector <ll> v;
		for (auto y : s[i]) v.pb(y.F);
		for (auto y : v) {
			s[i][y].insert({-inf, -1});
			s[i][y].insert({inf, -1});
			int la = -1;
			for (auto z : s[i][y]) {
				if (la == -1 || z.S == -1) {la = z.S; continue;}
				if (con[ty[la]][ty[z.S]]) m.insert({dis(la, z.S), {la, z.S}});
				la = z.S;
			}
		}
	}
	
	
	while (!m.empty()) {
		auto p = m.begin();
		ll d = p -> F;
		vector <int> v;
		while (!m.empty() && p -> F == d) {
			v.pb(p -> S.F);
			v.pb(p -> S.S);
			p = m.erase(p);
		}
		for (auto x : v) {
			if (res[x]) continue;
			res[x] = 1;
			for (auto y : wh[ty[x]]) rem(x, po[x][y].S, y);
		}
	}
	
	for (int i = 0; i < n; i++) if (!res[i]) cout << i+1 << "\n";

	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: 24 / 24