Submission #843771

#	Time	Username	Problem	Language	Result	Execution time	Memory
843771		TranGiaHuy1508	Robot Contest (IOI23_robot)	C++17	96 / 100	167 ms	14600 KiB

robot

#include <bits/stdc++.h>
using namespace std;

#include "robot.h"

enum State {
	BOUNDARY	= -2,
	OBSTACLE	= -1,
	EMPTY		= 0,
	MAIN		= 1,

	WEST		= 2,
	SOUTH		= 3,
	EAST		= 4,
	NORTH		= 5,
	
	BFS			= 6,
	RESOLVE		= 7,

	EVERYTHING	= -42,
	BLOCKED		= -3,
	DIRECTIONS	= -4,
	KEEP		= -5,
};

enum Move {
	M_STAY		= 'H',
	M_WEST		= 'W',
	M_SOUTH		= 'S',
	M_EAST		= 'E',
	M_NORTH		= 'N',
	M_TERMINATE	= 'T',
};

State clockwise(State S){
	if (S == NORTH) return EAST;
	if (S == EAST) return SOUTH;
	if (S == SOUTH) return WEST;
	if (S == WEST) return NORTH;
	return S;
}

State opposite(State S){
	return clockwise(clockwise(S));
}

State counter_clockwise(State S){
	return clockwise(opposite(S));
}

inline int idx(State S){
	assert(S >= 2 && S <= 5);
	return S - 1;
}

Move dirmove(State S){
	if (S == WEST) return M_WEST;
	if (S == SOUTH) return M_SOUTH;
	if (S == EAST) return M_EAST;
	if (S == NORTH) return M_NORTH;
	assert((false));
}

template <class T>
vector<T> operator + (const vector<T> &A, const vector<T> &B){
	vector<T> res = A;
	res.insert(res.end(), B.begin(), B.end());
	return res;
}

vector<State> expand(State S){
	if (S == BLOCKED) return {BOUNDARY, OBSTACLE};
	if (S == DIRECTIONS) return {WEST, SOUTH, EAST, NORTH};
	if (S == EVERYTHING){
		return expand(BLOCKED) + expand(DIRECTIONS)
		+ vector{EMPTY, MAIN, BFS, RESOLVE};
	}
	return {S};
}

namespace Script {
	static const int arrLen = 5;
	using StateArray = array<State, arrLen>;
	using Instruction = pair<State, Move>;

	StateArray everything(){
		StateArray res;
		for (int i = 0; i < arrLen; i++) res[i] = EVERYTHING;
		return res;
	}

	map<StateArray, Instruction> mp;

	template <bool OVERWRITE = false>
	void program(vector<vector<State>> S, Instruction _I){
		for (auto s0: S[0]) for (auto s1: S[1]) for (auto s2: S[2])
		for (auto s3: S[3]) for (auto s4: S[4]) {
			StateArray arr = {s0, s1, s2, s3, s4};
			if (!OVERWRITE && mp.count(arr)) continue;
			Instruction I = {_I.first == KEEP ? arr[0] : _I.first, _I.second};
			mp[arr] = I;
		}
	}

	template <bool OVERWRITE = false>
	void program(StateArray S, Instruction I){
		vector<vector<State>> expanded(arrLen);
		for (int i = 0; i < arrLen; i++){
			expanded[i] = expand(S[i]);
		}
		program<OVERWRITE>(expanded, I);
	}

	void set_all_instruction(){
		for (auto [S, I]: mp){
			vector<int> vS(begin(S), begin(S) + arrLen);
			set_instruction(vS, I.first, I.second);
		}
	}
}

void program_pulibot(){
	// Rule 1: Start at BFS
	{
		auto arr = Script::everything();
		arr[0] = EMPTY;
		arr[idx(WEST)] = BOUNDARY;
		arr[idx(NORTH)] = BOUNDARY;

		Script::program(arr, {BFS, M_STAY});
	}

	// Rule 2: Pull empty squares
	// Subrule 2.1: If we can pull, move to empty square
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = RESOLVE;
		arr[idx(d)] = EMPTY;

		Script::program(arr, {RESOLVE, dirmove(d)});
	}
	
	// Subrule 2.2: Return to old RESOLVE square
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = EMPTY;
		arr[idx(d)] = RESOLVE;

		Script::program(arr, {d, dirmove(d)});
	}

	// Subrule 2.3: If we cannot pull anymore, change to EMPTY
	// Moved below for ordering with Subrule 5.1

	// Rule 3: BFS
	// Subrule 3.1: If we can move to child square, move to it
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = BFS;
		arr[idx(d)] = opposite(d);

		Script::program(arr, {BFS, dirmove(d)});
	}

	// Subrule 3.2: If this points to a BFS square, change to BFS
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = d;
		arr[idx(d)] = BFS;

		Script::program(arr, {BFS, M_STAY});
	}

	// Subrule 3.3: If we cannot move anymore, change to RESOLVE
	{
		auto arr = Script::everything();
		arr[0] = BFS;

		Script::program(arr, {RESOLVE, M_STAY});
	}

	// Subrule 3.4: If empty and next to BFS, move
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = EMPTY;
		arr[idx(d)] = BFS;

		Script::program(arr, {EMPTY, dirmove(d)});
	}

	// Rule 4: Mark (H-1, W-1) as MAIN
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = EMPTY;
		arr[idx(d)] = RESOLVE;

		if (d == SOUTH || d == EAST) continue;
		arr[idx(SOUTH)] = BOUNDARY;
		arr[idx(EAST)] = BOUNDARY;

		Script::program<true>(arr, {MAIN, dirmove(d)});
	}

	// Rule 5: Cleanup
	// Subrule 5.1: If at RESOLVE, cannot move but next to MAIN, change to MAIN
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = RESOLVE;
		arr[idx(d)] = MAIN;

		Script::program(arr, {MAIN, M_STAY});
	}

	// Subrule 5.2: If at BFS and next to MAIN, change to RESOLVE
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = BFS;
		arr[idx(d)] = MAIN;

		Script::program<true>(arr, {RESOLVE, M_STAY});
	}

	// Subrule 5.2: If at MAIN or DIRECTIONS and can move to child square, move
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[idx(d)] = opposite(d);

		arr[0] = MAIN;
		Script::program(arr, {KEEP, dirmove(d)});

		arr[0] = DIRECTIONS;
		Script::program(arr, {KEEP, dirmove(d)});
	}

	// Subrule 5.3: If at DIRECTIONS and cannot move, mark EMPTY and return
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = d;

		Script::program(arr, {EMPTY, dirmove(d)});
	}

	// Subrule 5.4: If at MAIN and cannot move to child square, move to BFS
	for (State d: expand(DIRECTIONS)){
		auto arr = Script::everything();
		arr[0] = MAIN;
		arr[idx(d)] = BFS;

		Script::program(arr, {MAIN, dirmove(d)});
	}

	// Subrule 2.3: If we cannot pull anymore, change to EMPTY
	{
		auto arr = Script::everything();
		arr[0] = RESOLVE;

		Script::program(arr, {EMPTY, M_STAY});
	}

	// Rule 6: Termination
	{
		auto arr = Script::everything();

		Script::program(arr, {MAIN, M_TERMINATE});
	}

	Script::set_all_instruction();
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 20 / 20
• Subtask 5: 42.0000000018 / 46