Submission #417626

#	Time	Username	Problem	Language	Result	Execution time	Memory
417626		maximath_1	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	873 ms	876 KiB

Anna

#include "Anna.h"
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

/*
	L=14 -> 9 chebyshev_dist <= 1, 4 chebyshev_dist >= 2, 1 compass
	L=13 -> 7 chebyshev_dist <= 1, 4 chebyshev_dist >= 2, 2 different numbers for compass
	L=12 -> 7 chebyshev_dist <= 1, 4 chebyshev_dist >= 2, 1 number for compass
	// for 2 unused groups A and B, one of them must be {(0, 1), (1, 0), (1, 1), (1, -1)} away from the other
	// we can use this as a visual compass
*/

const int xx[] = {0, 1, 1, 1};
const int yy[] = {1, 0, 1, -1};

void Anna(int N, int K, vector<int> R, vector<int> C) {
	int tmp_occ[3][3];
	memset(tmp_occ, 0, sizeof(tmp_occ));
	for(int i = 0; i < K; i ++)
		tmp_occ[R[i] % 3][C[i] % 3] = 1;

	vector<pair<int, int> > unassigned_groups;
	for(int i = 0; i < 3; i ++)
		for(int j = 0; j < 3; j ++)
			if(!tmp_occ[i][j])
				unassigned_groups.push_back({i, j});

	unassigned_groups.resize(2);
	bool is_compass = 0;
	for(int d = 0; d < 4; d ++){
		if(make_pair((unassigned_groups[0].first + 3 + xx[d]) % 3, (unassigned_groups[0].second + 3 + yy[d]) % 3) == unassigned_groups[1])
			is_compass = 1;
	}
	if(!is_compass) swap(unassigned_groups[0], unassigned_groups[1]);

	int group[3][3], cnt = 0;
	for(int i = 0; i < 3; i ++){
		for(int j = 0; j < 3; j ++){
			if(i == 0 && j == 0) group[(unassigned_groups[0].first + i) % 3][(unassigned_groups[0].second + j) % 3] = -1;
			else if((unassigned_groups[0].first + i) % 3 == unassigned_groups[1].first && (unassigned_groups[0].second + j) % 3 == unassigned_groups[1].second)
				group[(unassigned_groups[0].first + i) % 3][(unassigned_groups[0].second + j) % 3] = -1;
			else group[(unassigned_groups[0].first + i) % 3][(unassigned_groups[0].second + j) % 3] = cnt ++;
		}
	}

	for(int i = 0; i < N; i ++){
		for(int j = 0; j < N; j ++){
			int gt = group[i % 3][j % 3];
			if(gt == -1) SetFlag(i, j, 12);
			else{
				int di = R[gt] - i, dj = C[gt] - j;
				if(dj >= 2) SetFlag(i, j, 1);
				else if(dj <= -2) SetFlag(i, j, 2);
				else if(di >= 2) SetFlag(i, j, 3);
				else if(di <= -2) SetFlag(i, j, 4);
				else{
					int cnt = -1, done = 0;
					for(int dx = -1; dx <= 1 && !done; dx ++)
						for(int dy = -1; dy <= 1 && !done; dy ++){
							int ni = i + dx, nj = j + dy;
							if(group[(ni + 3) % 3][(nj + 3) % 3] == -1) continue;
							cnt ++;
							if(ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
							if(ni == R[gt] && nj == C[gt]){
								SetFlag(i, j, cnt + 5);
								done = 1;
								break;
							}
						}
				}
			}
		}
	}
}

Bruno

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

const int xxx[] = {0, 1, 1, 1};
const int yyy[] = {1, 0, 1, -1};

vector<int> Bruno(int K, vector<int> value) {
	vector<int> ans(K, 0);

	vector<pair<int, int> > unassigned_groups;
	for(int i = 0; i < 3; i ++){
		for(int j = 0; j < 3; j ++){
			if(value[3 * i + j] == 12)
				unassigned_groups.push_back({i, j});
		}
	}

	bool is_compass = 0;
	for(int d = 0; d < 4; d ++){
		if(make_pair((unassigned_groups[0].first + 3 + xxx[d]) % 3, (unassigned_groups[0].second + 3 + yyy[d]) % 3) == unassigned_groups[1])
			is_compass = 1;
	}
	if(!is_compass) swap(unassigned_groups[0], unassigned_groups[1]);

	int group[3][3], cnt = 0;
	for(int i = 0; i < 3; i ++){
		for(int j = 0; j < 3; j ++){
			if(i == 0 && j == 0) group[(unassigned_groups[0].first + i) % 3][(unassigned_groups[0].second + j) % 3] = -1;
			else if((unassigned_groups[0].first + i) % 3 == unassigned_groups[1].first && (unassigned_groups[0].second + j) % 3 == unassigned_groups[1].second)
				group[(unassigned_groups[0].first + i) % 3][(unassigned_groups[0].second + j) % 3] = -1;
			else group[(unassigned_groups[0].first + i) % 3][(unassigned_groups[0].second + j) % 3] = cnt ++;
		}
	}

	for(int i = 0; i < 3; i ++)
		for(int j = 0; j < 3; j ++){
			int gt = group[i][j], tp = value[3 * i + j];
			if(gt == -1) continue;
			if(tp < 5)
				ans[gt] = tp - 1;
			else{
				tp -= 5;
				int cnt = -1, done = 0;
				for(int dx = -1; dx <= 1 && !done; dx ++)
					for(int dy = -1; dy <= 1 && !done; dy ++){
						int ni = i + dx, nj = j + dy;
						if(group[(ni + 3) % 3][(nj + 3) % 3] == -1) continue;
						cnt ++;
						if(cnt == tp){
							if(nj > 1) ans[gt] = 0;
							else if(nj < 1) ans[gt] = 1;
							else if(ni > 1) ans[gt] = 2;
							else if(ni < 1) ans[gt] = 3;
							else ans[gt] = 4;
						}
					}
			}
		}

	return ans;
}

• Subtask 1: 100 / 100