Submission #666832

#	Time	Username	Problem	Language	Result	Execution time	Memory
666832		rainboy	Navigation 2 (JOI21_navigation2)	C++17	85 / 100	782 ms	888 KiB

Anna

#include "Anna.h"
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace {
	char bad[3][3];
}

void Anna(int n, int k, vi ii, vi jj) {
	memset(bad, 0, sizeof bad);
	for (int h = 0; h < k; h++)
		bad[(h / 3 - ii[h] % 3 + 3) % 3][(h % 3 - jj[h] % 3 + 3) % 3] = 1;
	int i_, j_;
	for (i_ = 0; i_ < 3; i_++)
		for (j_ = 0; j_ < 3; j_++)
			if (!bad[i_][j_])
				goto out;
out:
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			int h = (i + i_) % 3 * 3 + (j + j_) % 3;
			if (h == 7 || h == 8) {
				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);
				if (d > 4)
					d--;
				SetFlag(i, j, 6 + d);
			}
		}
}

Bruno

#include "Bruno.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace B {
	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 i_, j_;
	for (i_ = 0; i_ < 3; i_++)
		for (j_ = 0; j_ < 3; j_++)
			if (B::aa[i_][j_] == 1 && B::aa[i_][(j_ + 1) % 3] == 1) {
				i_ = (i_ + 1) % 3, j_ = (j_ + 2) % 3;
				goto out;
			}
out:
	vi dir(k, 0);
	for (int h = 0; h < 7; h++) {
		int i = (i_ + h / 3) % 3, j = (j_ + h % 3) % 3, a = B::aa[i][j];
		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 >= 4)
				a++;
			int di = a / 3 - i, dj = a % 3 - j;
			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: 85 / 100