Submission #386333

#	Time	Username	Problem	Language	Result	Execution time	Memory
386333		model_code	Navigation 2 (JOI21_navigation2)	C++17	75 / 100	1208 ms	1428 KiB

Anna

#include <vector>
#include <algorithm>
#include "Anna.h"
 
namespace {
	int encode(int dr, int dc) {
		if(dc >= +2) return 2;
		if(dc <= -2) return 3;
		if(dr >= +2) return 4;
		if(dr <= -2) return 5;
		return (dr + 1) * 3 + (dc + 1) + 6;
	}
}
 
void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
	// Step #1 : Decide placement of "flags with number 1"
	int optflag = 14; int optdelta = -1;
	for(int delta = 0; delta < 9; ++delta) {
		int maxflag = 1;
		for(int i = 0; i < N; ++i) {
			for(int j = 0; j < N; ++j) {
				int precinct = ((i - delta / 3 + 3) % 3) * 3 + ((j - delta % 3 + 3) % 3);
				if(precinct <= 6) {
					maxflag = std::max(maxflag, encode(R[precinct] - i, C[precinct] - j));
				}
			}
		}
		if(optflag > maxflag) {
			optflag = maxflag;
			optdelta = delta;
		}
	}
	
	// Step #2 : Make a provisional plan
	std::vector<std::vector<int> > F(N, std::vector<int>(N, -1));
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			int precinct = ((i - optdelta / 3 + 3) % 3) * 3 + ((j - optdelta % 3 + 3) % 3);
			if(precinct <= 6) {
				F[i][j] = encode(R[precinct] - i, C[precinct] - j);
			}
			if(precinct == 8) {
				F[i][j] = 1;
			}
		}
	}
	
	// Step #3. Apply "decrease-by-1" operation and finalize the plan
	std::vector<bool> used(14, false);
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			if(F[i][j] != -1) {
				used[F[i][j]] = true;
			}
		}
	}
	int non = std::find(used.begin() + 1, used.end(), false) - used.begin();
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			if(F[i][j] == -1) {
				F[i][j] = non - 1;
			}
			else if(F[i][j] > non) {
				--F[i][j];
			}
			SetFlag(i, j, F[i][j] + 2);
		}
	}
}

Bruno

#include <vector>
#include <utility>
#include <algorithm>
#include "Bruno.h"
 
std::vector<int> Bruno(int K, std::vector<int> value) {
	// Step #1. Restore the plan before "decrease-by-1" operation
    for (int &x : value) x -= 2;
  
	int center = std::find(value.begin(), value.end(), 1) - value.begin();
	int rp = (center / 3 + 1) % 3, cp = (center % 3 + 1) % 3;
	std::vector<int> precinct(9);
	for(int i = 0; i < 9; ++i) {
		precinct[i] = ((i / 3 - rp + 3) % 3) * 3 + ((i % 3 - cp + 3) % 3);
	}
	int seventh = std::find(precinct.begin(), precinct.end(), 7) - precinct.begin();
	int non = value[seventh] + 1;
	for(int i = 0; i < 9; ++i) {
		if(value[i] >= non) {
			++value[i];
		}
	}
	
	// Step #2. Determine the next actions
	std::vector<int> res(K, -1);
	for(int i = 0; i < K; ++i) {
		int ptr = std::find(precinct.begin(), precinct.end(), i) - precinct.begin();
		int id = value[ptr] - 2;
		if(id <= 3) {
			res[i] = id;
		}
		else {
			int isor = ((id - 4) / 3 - 1) + (ptr / 3 - 1);
			int isoc = ((id - 4) % 3 - 1) + (ptr % 3 - 1);
			if(isoc > 0) res[i] = 0;
			else if(isoc < 0) res[i] = 1;
			else if(isor > 0) res[i] = 2;
			else if(isor < 0) res[i] = 3;
			else res[i] = 4;
		}
	}
	return res;
}

• Subtask 1: 75 / 100