Submission #1208149

#TimeUsernameProblemLanguageResultExecution timeMemory
1208149NK_Toy (CEOI24_toy)C++20
Compilation error
0 ms0 KiB
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

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

using str = string;
template<class T> using V = vector<T>;
// template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vs = V<str>;
using vi = V<int>;

const int nax = 365, wax = 365;
bitset<wax * wax> pos[nax][nax];
int hor[nax][nax], ver[nax][nax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	memset(hor, 0, sizeof hor);
	memset(ver, 0, sizeof ver);

	int R, C, W, L; cin >> C >> R >> W >> L;

	int xw, yw, xl, yl; cin >> xw >> yw >> xl >> yl; 
	// --xw, --yw, --xl, --yl;

	vs A(R); for(auto& x : A) cin >> x;

	int er, ec; for(int r = 0; r < R; r++) for(int c = 0; c < C; c++) {
		if (A[r][c] == '*') {
			er = r, ec = c;
			A[r][c] = '.';
		}
	}

	for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) {
		pos[i][j].reset();
	}	

	for(int i = 0; i < R; i++) {
		for(int j = C - 1; j >= 0; j--) {
			if (j + 1 < C) hor[i][j] = hor[i][j + 1];
			if (A[i][j] == '.') hor[i][j]++;
			if (A[i][j] == 'X') hor[i][j] = 0;
			// cout << hor[i][j] << " ";
		}
		// cout << endl;
	}

	for(int j = 0; j < C; j++) {
		for(int i = R - 1; i >= 0; i--) {
			if (i + 1 < R) ver[i][j] = ver[i + 1][j];
			if (A[i][j] == '.') ver[i][j]++;
			if (A[i][j] == 'X') ver[i][j] = 0;
			// cout << ver[i][j] << " ";
		}	
		// cout << endl;
	}	

	bool ans = 0;
	V<array<int, 4>> q; q.pb({yl, xw, yw - yl, xl - xw});
	while(sz(q)) {
		int r = q.back()[0];
		int c = q.back()[1];
		int rx = q.back()[2];
		int cx = q.back()[3];

		q.pop_back();

		// cout << r << " " << c << " " << rx << " " << cx << endl;
		pos[r][c][rx * wax + cx] = 1;

		int rw = r + rx, cw = c, rl = r, cl = c + cx;
		// cout << rw << " " << cw << " | " << rl << " " << cl << endl;
		if (rw == er && cl == ec) {
			ans = 1;
			break;
		}

		// move vertical left
		if (cl - 1 >= 0 && cx - 1 >= 0 && ver[rl][cl - 1] >= L) {
			if (!pos[r][c][rx * wax + cx - 1]) q.pb({r, c, rx, cx - 1});
		}

		// move vertical right
		if (cl + 1 < C && cx + 1 < W && ver[rl][cl + 1] >= L) {
			if (!pos[r][c][rx * wax + cx + 1]) q.pb({r, c, rx, cx + 1});
		}

		// move vertical up
		if (rl - 1 >= 0 && rx + 1 < L && ver[rl - 1][cl] >= L) {
			if (!pos[r - 1][c][(rx + 1) * wax + cx]) q.pb({r - 1, c, rx + 1, cx});
		}

		// move vertical down
		if (rl + 1 < R && rx - 1 >= 0 && ver[rl + 1][cl] >= L) {
			if (!pos[r + 1][c][(rx - 1) * wax + cx]) q.pb({r + 1, c, rx - 1, cx});
		}

		// move horizontal up
		if (rw - 1 >= 0 && rx - 1 >= 0 && hor[rw - 1][cw] >= W) {
			if (!pos[r][c][(rx - 1) * wax + cx]) q.pb({r, c, rx - 1, cx});
		}

		// move horizontal down
		if (rw + 1 < R && rx + 1 < L && hor[rw + 1][cw] >= W) {
			if (!pos[r][c][(rx + 1) * wax + cx]) q.pb({r, c, rx + 1, cx});
		}

		// move horizontal left
		if (cw - 1 >= 0 && cx + 1 < W && hor[rw][cw - 1] >= W) {
			if (!pos[r][c - 1][rx * wax + cx + 1]) q.pb({r, c - 1, rx, cx + 1});
		}

		// move horizontal right
		if (cw + 1 < C && cx - 1 >= 0 && hor[rw][cw + 1] >= W) {
			if (!pos[r][c + 1][rx * wax + cx - 1]) q.pb({r, c + 1, rx, cx - 1});
		}
	}

	cout << (ans ? "YES" : "NO") << nl;

	exit(0-0);
}

// Breathe In, Breathe Out

Compilation message (stderr)

/tmp/cccDzhsA.o: in function `main':
Main.cpp:(.text.startup+0x12): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
Main.cpp:(.text.startup+0x34): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
Main.cpp:(.text.startup+0x92d): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
/tmp/cccDzhsA.o: in function `_GLOBAL__sub_I_pos':
Main.cpp:(.text.startup+0xaa8): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status