Submission #666876

#	Time	Username	Problem	Language	Result	Execution time	Memory
666876		rainboy	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	813 ms	928 KiB

Anna

#include "Anna.h"
#include <cassert>
#include <cstring>
#include <vector>
 
using namespace std;
 
typedef vector<int> vi;
 
namespace A {
	int hh[4][3][3] = {
		{ { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 } },
		{ { 0, 1, 2 }, { 7, 4, 5 }, { 6, 3, 8 } },
		{ { 0, 1, 2 }, { 3, 7, 5 }, { 6, 4, 8 } },
		{ { 0, 1, 2 }, { 3, 4, 7 }, { 6, 5, 8 } },
	};
	int dd[4] = { 3, 0, 1, 2 };
	char bad[3][3];
}
 
void Anna(int n, int k, vi ii, vi jj) {
	int g, i_, j_, d_, di_, dj_;
	for (g = 0; g < 4; g++) {
		d_ = A::dd[g], di_ = d_ / 3 - 1, dj_ = d_ % 3 - 1;
		memset(A::bad, 0, sizeof A::bad);
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++) {
				int h = A::hh[g][i][j];
				if (h >= k)
					continue;
				A::bad[(i - ii[h] % 3 + 3) % 3][(j - jj[h] % 3 + 3) % 3] = 1;
				A::bad[(i - (ii[h] + di_) % 3 + 3) % 3][(j - (jj[h] + dj_) % 3 + 3) % 3] = 1;
			}
		for (i_ = 0; i_ < 3; i_++)
			for (j_ = 0; j_ < 3; j_++)
				if (!A::bad[i_][j_])
					goto out;
	}
out:
	assert(g < 4);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			int h = A::hh[g][(i + i_) % 3][(j + j_) % 3];
			if (h >= k) {
				SetFlag(i, j, 1);
				continue;
			}
			int di = i - ii[h], dj = j - jj[h];
			if (di < -1)
				SetFlag(i, j, 2);
			else if (di > 1)
				SetFlag(i, j, 3);
			else if (dj < -1)
				SetFlag(i, j, 4);
			else if (dj > 1)
				SetFlag(i, j, 5);
			else {
				int d = (di + 1) * 3 + (dj + 1);
				assert(d != d_ && d != 4);
				if (d > 4)
					d--;
				if (d > d_)
					d--;
				SetFlag(i, j, 6 + d);
			}
		}
}

Bruno

#include "Bruno.h"
#include <vector>
 
using namespace std;
 
typedef vector<int> vi;
 
namespace B {
	int hh[4][3][3] = {
		{ { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 } },
		{ { 0, 1, 2 }, { 7, 4, 5 }, { 6, 3, 8 } },
		{ { 0, 1, 2 }, { 3, 7, 5 }, { 6, 4, 8 } },
		{ { 0, 1, 2 }, { 3, 4, 7 }, { 6, 5, 8 } },
	};
	int dd[4] = { 3, 0, 1, 2 };
	int aa[3][3];
}
 
vi Bruno(int k, vi aa_) {
	for (int ij = 0; ij < 9; ij++)
		B::aa[ij / 3][ij % 3] = aa_[ij];
	int g, d_, i_, j_;
	for (g = 0; g < 4; g++) {
		d_ = B::dd[g];
		for (i_ = 0; i_ < 3; i_++)
			for (j_ = 0; j_ < 3; j_++) {
				int good = 1;
				for (int i = 0; i < 3; i++)
					for (int j = 0; j < 3; j++)
						if ((B::aa[(i + i_) % 3][(j + j_) % 3] == 1) != (B::hh[g][i][j] >= k)) {
							good = 0;
							goto out1;
						}
out1:
				if (good)
					goto out2;
			}
	}
out2:
	vi dir(k, 0);
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++) {
			int h = B::hh[g][i][j];
			if (h >= k)
				continue;
			int a = B::aa[(i + i_) % 3][(j + j_) % 3];
			if (a == 2)
				dir[h] = 2;
			else if (a == 3)
				dir[h] = 3;
			else if (a == 4)
				dir[h] = 0;
			else if (a == 5)
				dir[h] = 1;
			else {
				a -= 6;
				if (a >= d_)
					a++;
				if (a >= 4)
					a++;
				int di = a / 3 - (i + i_) % 3, dj = a % 3 - (j + j_) % 3;
				if (di < 0)
					dir[h] = 2;
				else if (di > 0)
					dir[h] = 3;
				else if (dj < 0)
					dir[h] = 0;
				else if (dj > 0)
					dir[h] = 1;
				else
					dir[h] = 4;
			}
		}
	return dir;
}

• Subtask 1: 100 / 100