Submission #525218

#	Time	Username	Problem	Language	Result	Execution time	Memory
525218		amunduzbaev	Navigation 2 (JOI21_navigation2)	C++17	75 / 100	791 ms	996 KiB

Anna

#include "Anna.h"
#include "bits/stdc++.h"
using namespace std;
 
void Anna(int n, int k, vector<int> r, vector<int> c) {
	vector<vector<int>> f(n, vector<int>(n, -1));
	vector<vector<int>> t(n, vector<int>(n));
	//~ for(int i=0;i<k;i++) t[r[i]][c[i]] = i + 1;
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<n;j++){
			//~ cout<<t[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	int ch[9][2] = {
		{-1, -1},
		{-1, 0},
		{-1, 1},
		{0, -1},
		{0, 0},
		{0, 1},
		{1, -1},
		{1, 0},
		{1, 1}
	};
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int in = (i%3) * 3 + j%3;
			if(in){ in--;
				if(in == 7) { f[i][j] = 1; continue; }
				if(c[in] > j + 1){
					f[i][j] = 0;
				} else if(r[in] > i + 1){
					f[i][j] = 2;
				} else if(c[in] < j - 1){
					f[i][j] = 1;
				} else if(r[in] < i - 1){
					f[i][j] = 3;
				} else {
					for(int t=0;t<9;t++){
						int x = i + ch[t][0], y = j + ch[t][1];
						if(r[in] == x && c[in] == y){
							f[i][j] = t + 4;
						}
					}
				} f[i][j]++;
			} else {
				f[i][j] = 0;
			}
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			assert(~f[i][j]);
			SetFlag(i, j, f[i][j] + 1);
		}
	}
}

Bruno

#include "Bruno.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array

vector<int> Bruno(int k, vector<int> val) {
	vector<int> r(k), ii(9);
	ar<int, 2> ch[9] = {
		{-1, -1},
		{-1, 0},
		{-1, 1},
		{0, -1},
		{0, 0},
		{0, 1},
		{1, -1},
		{1, 0},
		{1, 1}
	};
	
	int is = -1;
	ar<int, 2> p = {-2};
	for(int i=0;i<9;i++){ val[i]--;
		if(val[i]) continue;
		is = i; p = ch[i];
	} assert(~is);
	
	for(int i=0;i<9;i++){
		int x = 3 + ch[i][0] - p[0], y = 3 + ch[i][1] - p[1];
		ii[i] = (x % 3) * 3 + (y % 3);
	}
	
	for(int i=0;i<9;i++){
		if(ii[i] == 0 || ii[i] == 8) continue;
		int in = ii[i] - 1, f = val[i] - 1;
		
		if(f < 4) r[in] = f;
		else { f -= 4;
			int x = ch[i][0] + ch[f][0], y = ch[i][1] + ch[f][1];
			if(y > 0) r[in] = 0;
			else if(x > 0) r[in] = 2;
			else if(y < 0) r[in] = 1;
			else if(x < 0) r[in] = 3;
			else r[in] = 4;
		}
	} 
	
	//~ for(int i=0;i<k;i++) cout<<r[i]<<" ";
	//~ cout<<"\n";
	return r;
}

• Subtask 1: 75 / 100