Submission #533327

#	Time	Username	Problem	Language	Result	Execution time	Memory
533327		fhvirus	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	848 ms	1008 KiB

Anna

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

namespace {

const int kMark = 13;

std::vector<std::vector<int>> flag;
void init(const int& N) {
	flag.assign(N, std::vector<int>(N, 0));
}
int get_val(const int& i, const int& j, const int& r, const int& c) {
	if (j <= c - 2) return  9;
	if (j >= c + 2) return 10;
	if (i <= r - 2) return 11;
	if (i >= r + 2) return 12;
	int di = i - r, dj = j - c;
	int val = (di + 1) * 3 + (dj + 1) + 1;
	return (val == 9 ? -1 : val);
}
bool solve(const int& N, const int& K, const std::vector<int>& R, const std::vector<int>& C, const int& offset) {
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) {
			int k = ((i + offset / 3) % 3) * 3 + ((j + offset % 3) % 3);
			flag[i][j] = (k < 7 ? get_val(i, j, R[k], C[k]) : (k == 8 ? kMark : 0));
			if (flag[i][j] == -1) return false;
		}
	return true;
}

} // namespace

void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
	init(N);

	for (int i = 0; i < 9; ++i)
		if (solve(N, K, R, C, i)) break;

	std::vector<bool> used(kMark + 1, false);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			used[flag[i][j]] = true;

	int no_use;
	for (int i = 0; i <= kMark; ++i)
		if (!used[i]) {
			no_use = i;
			break;
		}

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) {
			if (flag[i][j] > no_use) --flag[i][j];
			if (flag[i][j] == 0) flag[i][j] = no_use;
      SetFlag(i, j, flag[i][j]);
		}
}

Bruno

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

namespace {

const int kMark = 12;

int judge(const int& i, const int& j, const int& r, const int& c) {
	if (i == r and j == c) return 4;
	if (j < c) return 0;
	if (j > c) return 1;
	if (i < r) return 2;
	if (i > r) return 3;
	return -1;
}

} // namespace

std::vector<int> Bruno(int K, std::vector<int> value) {
	int mark_i, mark_j, no_use;
	for (int i = 0; i < 9; ++i)
		if (value[i] == kMark) {
			mark_i = i / 3;
			mark_j = i % 3;
		}
	no_use = value[mark_i * 3 + (mark_j + 2) % 3];

	std::vector<int> res(K);
	for (int dk = 0; dk < 9; ++dk) {
		int i = (dk / 3 + 2 - mark_i) % 3, j = (dk % 3 + 2 - mark_j) % 3;
		int k = i * 3 + j;
		if (i * 3 + j >= 7) continue;
		if (value[dk] >= no_use) ++value[dk];
		if (value[dk] >= 9) res[k] = value[dk] - 9;
		else {
			int r = dk / 3 + (1 - (value[dk] - 1) / 3);
			int c = dk % 3 + (1 - (value[dk] - 1) % 3);
			res[k] = judge(1, 1, r, c);
		}
	}

	return res;
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, int, std::vector<int>, std::vector<int>)':
Anna.cpp:55:36: warning: 'no_use' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |    if (flag[i][j] == 0) flag[i][j] = no_use;

Bruno.cpp: In function 'std::vector<int> Bruno(int, std::vector<int>)':
Bruno.cpp:31:54: warning: 'mark_j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |   int i = (dk / 3 + 2 - mark_i) % 3, j = (dk % 3 + 2 - mark_j) % 3;
      |                                          ~~~~~~~~~~~~^~~~~~~~~
Bruno.cpp:31:23: warning: 'mark_i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |   int i = (dk / 3 + 2 - mark_i) % 3, j = (dk % 3 + 2 - mark_j) % 3;
      |           ~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 100 / 100