Submission #415124

#	Time	Username	Problem	Language	Result	Execution time	Memory
415124		Namnamseo	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	937 ms	892 KiB

Anna

#include "Anna.h"
#include <utility>
using namespace std;
using pii=pair<int,int>;

namespace {
pii pos[7];

// [     10      ]
//      1 2 3 
// 11 | 4 5 6 | 13
//      7 8 9
// [     12     ]
//
int opinion(int r, int c, int target)
{
	int dr = pos[target].first - r;
	int dc = pos[target].second - c;
	if (dr >= 2) return 12;
	if (dc >= 2) return 13;
	if (dr <= -2) return 10;
	if (dc <= -2) return 11;
	return (dr+1)*3 + (dc+1) + 1;
}

int ancr, ancc, off;
int get_type(int r, int c) { return (r+3-ancr)%3 * 3 + (c+3-ancc)%3; }
void find_anchor()
{
	for (ancr=0; ancr<3; ++ancr) for (ancc=0; ancc<3; ++ancc) {
		bool ok = 1;
		for (int i=0; i<7; ++i) {
			auto [r, c] = pos[i];
			int nine_type = get_type(r-1, c-1);
			if (nine_type == i) {
				ok = 0; break;
			}
		}
		if (ok) return;
	}
}
bool is_anchor(int i, int j) { return i%3 == ancr && j%3 == ancc; }

int raw[110][110];
bool is_used[20];

}

void Anna(int n, int k, vector<int> r, vector<int> c)
{
	for (int i=0; i<k; ++i) pos[i] = {r[i], c[i]};
	find_anchor();

	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j) {
			int type = get_type(i, j);
			if (type < 7) {
				raw[i][j] = opinion(i, j, type);
			} else if (type == 7) {
				raw[i][j] = 14;
			} else {
				raw[i][j] = 14;
			}
		}
	}

	for (int i=1; i<=14; ++i) is_used[i] = false;
	for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) {
		is_used[raw[i][j]] = true;
	}

	if (is_used[9]) throw "oh no";
	int hi = -1;
	for (int i=1; i<9; ++i) if (!is_used[i]) { hi = i; break; }

	for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) {
		int ans;
		switch(get_type(i, j)) {
		case 8: ans = 12; break;
		case 7: ans = hi; break;
		default:
			int v = raw[i][j];
			if (v >= 9) ans = v-2;
			else if (v >= hi) ans = v-1;
			else ans = v;
		}
		SetFlag(i, j, ans);
	}
}

Bruno

#include "Bruno.h"
#include <iostream>
using namespace std;

vector<int> Bruno(int k, vector<int> value)
{
	int val_map[3][3];
	int type_map[3][3];
	for (int i=0; i<9; ++i) val_map[i/3][i%3] = value[i];
	int ar, ac;
	[&]{ for (ar=0; ar<3; ++ar) for (ac=0; ac<3; ++ac) {
		if (val_map[ar][ac] == 12) return;
	} }();
	for (int dr=0; dr<3; ++dr) for (int dc=0; dc<3; ++dc) {
		type_map[(ar+dr)%3][(ac+dc)%3] = (
			((dr+2)%3)*3 + (dc+2)%3
		);
	}

	int hi;
	for (int r=0; r<3; ++r) for (int c=0; c<3; ++c) if (type_map[r][c] == 7) {
		hi = val_map[r][c];
	}

	for (int r=0; r<3; ++r) for (int c=0; c<3; ++c) if (type_map[r][c] != 8) {
		int &v = val_map[r][c];
		if (v >= hi) ++v;
		if (v >= 9) ++v;
	}

	vector<int> ret;
	for (int i=0; i<7; ++i) {
		int tr, tc;
		[&]{ for (tr=0; tr<3; ++tr) for (tc=0; tc<3; ++tc) {
			if (type_map[tr][tc] == i) return;
		} }();

		int v = val_map[tr][tc];
		int ans;

		if (v == 10) ans = 3;
		else if (v == 11) ans = 1;
		else if (v == 12) ans = 2;
		else if (v == 13) ans = 0;
		else {
			int dr = (v-1)/3 - 1;
			int dc = (v-1)%3 - 1;

			int ir = tr+dr, ic = tc+dc;
			if (ir == 1 && ic == 1) {
				ans = 4;
			} else if (ir <= 0) {
				ans = 3;
			} else if (ir >= 2) {
				ans = 2;
			} else if (ic <= 0) {
				ans = 1;
			} else if (ic >= 2) {
				ans = 0;
			}
		}

		ret.push_back(ans);
	}

	return ret;
}

Compilation message (stderr)

Anna.cpp:42:6: warning: 'bool {anonymous}::is_anchor(int, int)' defined but not used [-Wunused-function]
   42 | bool is_anchor(int i, int j) { return i%3 == ancr && j%3 == ancc; }
      |      ^~~~~~~~~
Anna.cpp:26:17: warning: '{anonymous}::off' defined but not used [-Wunused-variable]
   26 | int ancr, ancc, off;
      |                 ^~~

Bruno.cpp: In function 'std::vector<int> Bruno(int, std::vector<int>)':
Bruno.cpp:27:3: warning: 'hi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |   if (v >= hi) ++v;
      |   ^~

• Subtask 1: 100 / 100