제출 #1194465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194465		franuch	Naval battle (CEOI24_battle)	C++20	0 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define vc vector
#define pub push_back
#define pob pop_back
#define st first
#define nd second

const ll C = 10;
vc<vc<pll>> grid(C, vc<pll>(C, {-1, -1}));

pll nxt(ll x, ll y) {
	ll dir = grid[y][x].st;
	if (dir == 0)
		return {x, y - 1};
	if (dir == 1)
		return {x, y + 1};
	if (dir == 2)
		return {x + 1, y};
	return {x - 1, y};
}

bool valid(ll x, ll y) {
	return 0 <= x and x < C and 0 <= y and y < C;
}

void program() {
	ll n;
	cin >> n;
	for (ll i = 0; i < n; i++) {
		ll x, y;
		cin >> x >> y;
		char dir;
		cin >> dir;
		if (dir == 'N')
			grid[y][x] = {0, i};
		else if (dir == 'S')
			grid[y][x] = {1, i};
		else if (dir == 'E')
			grid[y][x] = {2, i};
		else
			grid[y][x] = {3, i};
	}

	vc<bool> git(n);
	while (true) {
		/*
		for (ll y = 0; y < C; y++) {
			for (ll x = 0; x < C; x++) {
				cerr << " ";
				if (grid[y][x].st != -1)
					cerr << grid[y][x].st;
				else
					cerr << ".";
			}
			cerr << "\n";
		}
		cerr << "\n";
		*/
		bool good = false;
		vc<vc<ll>> occ(C, vc<ll>(C, 0));
		for (ll y = 0; y < C; y++)
			for (ll x = 0; x < C; x++) {
				ll dir = grid[y][x].st;
				ll i = grid[y][x].nd;
				if (dir != -1)
					good = true;
				else
					continue;
			
				auto [z, t] = nxt(x, y);
				if (valid(z, t))
					occ[t][z]++;
				else
					git[i] = true;
			}
		if (not good)
			break;

		vc<vc<pll>> tmp(C, vc<pll>(C, {-1, -1}));
		for (ll y = 0; y < C; y++)
			for (ll x = 0; x < C; x++) {
				ll dir = grid[y][x].st;
				if (dir == -1)
					continue;
				auto [z, t] = nxt(x, y);
				if (valid(z, t) and occ[t][z] == 1)
					tmp[t][z] = grid[y][x];
			}
		swap(tmp, grid);
	}
	for (ll i = 0; i < n; i++)
		if (git[i])
			cout << i + 1 << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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