Submission #843716

#	Time	Username	Problem	Language	Result	Execution time	Memory
843716		TranGiaHuy1508	Robot Contest (IOI23_robot)	C++17	24 / 100	111 ms	8952 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,
	CLEANING	= 6,

	EVERYTHING	= -42,
	BLOCKED		= -3,
	DIRECTIONS	= -4,
	ENDING		= -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));
}

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

Move with_dir(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));
}

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

	map<StateArray, Instruction> mp;

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

	vector<State> group(State S){
		if (S == BLOCKED) return {BOUNDARY, OBSTACLE};
		if (S == DIRECTIONS) return {WEST, SOUTH, EAST, NORTH};
		if (S == ENDING) return {MAIN, BOUNDARY, OBSTACLE, EMPTY};
		if (S == EVERYTHING) return {
			BOUNDARY, OBSTACLE, EMPTY, MAIN, CLEANING,
			WEST, SOUTH, EAST, NORTH
		};
		return {S};
	}

	template <bool OVERWRITE = false>
	void program(StateArray S, Instruction I){
		vector<StateArray> arrs = {StateArray()};

		// Construct all possible StateArray(s)
		for (int i = 0; i < arrLen; i++){
			vector<StateArray> new_arrs;
			vector<State> repr = group(S[i]);

			for (auto arr: arrs){
				for (auto j: repr){
					new_arrs.push_back(arr);
					new_arrs.back()[i] = j;
				}
			}

			new_arrs.swap(arrs);
		}

		// Resolve
		for (auto arr: arrs){
			if (!OVERWRITE && mp.count(arr)) continue;
			mp[arr] = I;
		}
	}

	template <bool OVERWRITE = false>
	void program(StateArray S, State Z, Move A){
		return program<OVERWRITE>(S, {Z, A});
	}

	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 main_program();

void program_pulibot(){
	main_program();
	Script::set_all_instruction();
}

void main_program(){
	// Starting position
	Script::program<true>({
		EMPTY, BOUNDARY, EVERYTHING, EVERYTHING, BOUNDARY
	},
	NORTH,
	M_STAY);

	// Move forward
	for (State crr: Script::group(DIRECTIONS)){
		State nxt = clockwise(crr);
		
		Script::StateArray arr = Script::everything();
		arr[0] = crr;

		// Move to everything
		Script::program<false>(arr, nxt, M_STAY);

		// Move to empty square
		arr[dir_idx(nxt)] = EMPTY;
		Script::program<true>(arr, nxt, with_dir(nxt));

		// Move to child square
		arr[dir_idx(nxt)] = opposite(nxt);
		Script::program<true>(arr, nxt, with_dir(nxt));
	}

	// Empty square
	for (State indir: Script::group(DIRECTIONS)){
		Script::StateArray arr = Script::everything();
		arr[0] = EMPTY;
		arr[dir_idx(indir)] = opposite(indir);
		Script::program<false>(arr, indir, with_dir(indir));

		// If this is (H-1, W-1), mark as MAIN instead
		if (indir != EAST && indir != SOUTH){
			arr[dir_idx(EAST)] = BOUNDARY;
			arr[dir_idx(SOUTH)] = BOUNDARY;
			// Script::program<true>(arr, MAIN, with_dir(indir));
			Script::program<true>(arr, CLEANING, with_dir(indir));
		}
	}

	// If pointing to MAIN/CLEANING, mark as CLEANING
	for (State dir: Script::group(DIRECTIONS)){
		Script::StateArray arr = Script::everything();
		arr[0] = dir;

		arr[dir_idx(dir)] = MAIN;
		Script::program<true>(arr, CLEANING, M_STAY);

		arr[dir_idx(dir)] = CLEANING;
		Script::program<true>(arr, CLEANING, M_STAY);
	}

	// If currently CLEANING, and there is nothing to clean
	for (State dir: Script::group(DIRECTIONS)){
		Script::StateArray arr = Script::everything();

		arr[0] = CLEANING;

		// Moving to MAIN
		arr[dir_idx(dir)] = MAIN;
		Script::program<false>(arr, MAIN, with_dir(dir));

		// Moving to CLEANING
		arr[dir_idx(dir)] = CLEANING;
		Script::program<true>(arr, EMPTY, with_dir(dir));

		Script::StateArray tmparr = arr;
		// If there is a MAIN, change color to MAIN instead
		for (State maindir: Script::group(DIRECTIONS)){
			if (maindir == dir) continue;
			tmparr[dir_idx(maindir)] = MAIN;
			Script::program<true>(tmparr, MAIN, with_dir(dir));
			tmparr = arr;
		}

		arr = Script::everything();
		arr[0] = CLEANING;

		// If at start
		arr[dir_idx(NORTH)] = BOUNDARY;
		arr[dir_idx(WEST)] = BOUNDARY;

		if (dir != NORTH && dir != WEST){
			arr[dir_idx(dir)] = CLEANING;
			Script::program<true>(arr, MAIN, with_dir(dir));

			arr[dir_idx(dir)] = MAIN;
			Script::program<true>(arr, MAIN, with_dir(dir));
		}
	}

	// If currently CLEANING, and there is a path to clean
	for (State indir: Script::group(DIRECTIONS)){
		Script::StateArray arr = Script::everything();
		
		arr[0] = CLEANING;
		arr[dir_idx(indir)] = opposite(indir);

		Script::program<true>(arr, CLEANING, with_dir(indir));
	}

	// Termination
	Script::program<true>({
		MAIN, MAIN, BOUNDARY, BOUNDARY, EVERYTHING
	},
	MAIN,
	M_TERMINATE);

	Script::program<true>({
		MAIN, EVERYTHING, BOUNDARY, BOUNDARY, MAIN
	},
	MAIN,
	M_TERMINATE);

	Script::program<true>({
		MAIN, ENDING, ENDING, ENDING, ENDING
	},
	MAIN,
	M_TERMINATE);
}

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