Submission #521654

#	Time	Username	Problem	Language	Result	Execution time	Memory
521654		CaroLinda	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	1008 ms	872 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

#define mk make_pair

using namespace std ;


void Anna(int N, int K, vector<int> R, vector<int> C) {

	vector<bool> classes(9, false) ;
	int dx[9] = {0,0,1,-1,1,1,-1,-1, 0} , dy[9] = {1,-1,0,0, 1, -1, 1, -1, 0} ;

	for(int i = 0 ; i < K ; i++ ){
		int x = R[i]%3 ;
		int y = C[i]%3 ;
		int num = x*3 + y ;
		classes[num] = true ;
	}			

	vector<int> unused ;
	for(int i = 0 ; i < 9 && (int)unused.size() < 2; i++ )
		if(!classes[i] ) unused.push_back(i) ;

	vector<int> val(9,12) ;
	int lastVal = 0 ;

	auto getClass = [&](int a, int b) {
		a %= 3 ;
		a = (a+3)%3 ;
		b %= 3 ;
		b = (b+3)%3 ;

		return a*3 + b ;
	} ;

	vector<pair<int,int> > deltas = { mk(0,1) , mk(1,0) , mk(1,-1) , mk(1,1) } ;

	for(int i = 0 ; i < 2 ; i++ , swap(unused[0], unused[1] ) ) {
		bool ok = false ;

		int c = unused[1]/3 , d = unused[1]%3 ;

		for(auto e : deltas ) {
			int a = e.first+c ;
			int b = e.second+d ;
			if(getClass(a,b) == unused[0] ) ok = true ;			
      }

      if(ok) break ;
	}

	int a = unused[0]/3 , b = unused[0]%3 ;

	for(int i = 0 , q = 0 ; i < 8 ; i++ ){
		int na = a + dx[i] ;
		int nb = b + dy[i] ;
		if( getClass(na,nb) == unused[1] ) continue ;
		val[ getClass(na,nb) ] = q++ ;
	}	

	auto getDistance = [&](int a, int b, int p){
		int dx = abs(a-R[p]) ;
		int dy =abs(b-C[p] ) ;
		return dx+dy ;
	} ;

	for(int i = 0 ; i< N ; i++ ){
		for(int j= 0 ; j<N ; j++ ){

			if( getClass(i,j) == unused[0] || getClass(i,j) == unused[1] ){
				SetFlag(i,j,12) ;
				continue ;
			}

			if(val[ getClass(i,j) ] >= K ) { SetFlag(i,j,1) ; continue ; }

			int myParty = val[ getClass(i,j) ] ;
			int d = getDistance(i,j, myParty ) ;
			bool ok = false ;
			int idx = 1; 

			for(int g = 0 , ni , nj  ; g < 9 ; g++ ){
				ni = i+dx[g] ;
				nj = j+dy[g] ;

				if(getClass(ni,nj) == unused[0] || getClass(ni,nj) == unused[1] ) continue ;
				if( getDistance(ni,nj,myParty ) == 0 ){
					SetFlag(i,j,idx) ;
					ok = true ;
					break ;
				}
				idx++ ;
			}

			if(ok) continue ;

			if(C[myParty]-j >= 2 ) SetFlag(i,j,8) ;
			else if(j-C[myParty] >= 2 ) SetFlag(i,j,9) ;
			else if( R[myParty]-i >= 2 ) SetFlag(i,j,10) ;
			else SetFlag(i,j,11) ;

		}
	}


}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

#define mk make_pair
#define debug printf

using namespace std ;

std::vector<int> Bruno(int K, std::vector<int> value) {

	auto getClass = [&](int a, int b){
		a = a%3 ;
		a = (a+3)%3 ;
		b = b%3 ;
		b = (b+3)%3 ;
		return a*3 + b ;
	} ;


	int dx[9] = {0,0,1,-1,1,1,-1,-1, 0} , dy[9] = {1,-1,0,0, 1, -1, 1, -1, 0} ;

	vector<pair<int,int> > vec ;
	vector< vector<int> > grid(3, vector<int>(3) ) , party(3, vector<int>(3,-1) ) ;

	for(int i = 0 , a = 0 , b = 0 ; i < 9 ; i++ , b++ ){
		if(b == 3 ) a++ , b = 0 ;
		grid[a][b] = value[i] ;
		if(value[i] == 12 ) vec.push_back(make_pair(a,b) ) ;
	}
	
	vector<pair<int,int> > deltas = { mk(0,1) , mk(1,0) , mk(1,-1) , mk(1,1) } ;

	for(int i = 0 ; i < 2 ; i++ , swap(vec[0], vec[1] ) ){
		bool ok = false ;


		for(auto e : deltas ) {
			int x = vec[1].first+e.first ;
			int y = vec[1].second+e.second ;
			if(getClass(x,y) == getClass( vec[0].first, vec[0].second ) ) ok = true ;
      }

      if(ok) break ;
	}
   
	auto getDistance = [&](int a, int b, int c, int d){
		int dx = abs(a-c) ;
		int dy = abs(b-d) ;
		return dx + dy ;
	} ;

	auto getDirection = [&](int a, int b, int c, int d ){
		if( a == c && b == d ) return 4 ;		
		for(int i = 0 , na , nb ; i < 4 ; i++ ){
			na = a + dx[i] ;
			nb = b + dy[i] ;
			if(getDistance(na,nb,c,d) >= getDistance(a,b,c,d) ) continue ;
			return i ;
		}
	} ;

	int num = getClass(vec[0].first, vec[0].second) ;
	int x = num+1 ;

	vector<int> val(9,-1) ;

	for( int i = 0, q = 0 ; i< 8 ; i++ ){
		int na = vec[0].first+dx[i] ;
		int nb = vec[0].second + dy[i] ;
		if( getClass(na,nb) == getClass(vec[1].first, vec[1].second) ) continue ;

		val[ getClass(na,nb) ] = q++ ;
	}

/*	cout << vec[0].first <<" " << vec[0].second << " " << vec[1].first <<" " << vec[1].second << endl ;

	cout << "Printing grid" << endl ;
	for(int i = 0 ; i < 3 ; i++ , cout << endl )
		for(int j = 0 ; j < 3 ; j++ ) cout << grid[i][j] <<" " ; */

	for(int i = 0 ; i < 3 ; i++ )
		for(int j = 0 ; j< 3 ; j++ ) party[i][j] = val[ getClass(i,j) ] ;

	vector<int> ans(K,-1) ;
	vector<int> unused = { getClass(vec[0].first, vec[0].second), getClass(vec[1].first, vec[1].second) } ;

	for(int i = 0 ; i < 3 ; i++ )
		for(int j = 0 ; j < 3 ; j++ ){

			if( grid[i][j] == 12 || party[i][j] >= K ) {
				continue ;
			}

			if( grid[i][j] >= 8 ){

				int mov = grid[i][j]-8 ;
				ans[ party[i][j] ]=mov ;

				continue ;
			}			

			int idx =1  , A , B ;
			for(int g = 0 ; g < 9 ; g++ ){

				int code=getClass(dx[g]+i , dy[g]+j) ;

				if( code == unused[0] || code == unused[1] ) continue ;

				if( idx == grid[i][j] ){
					A = dx[g]+i ;
					B = dy[g] + j ;					
					break ;
				}

				idx++ ;
			}

			ans[ party[i][j] ]  = getDirection(1,1,A,B) ;

		}

	return ans ;

}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, int, std::vector<int>, std::vector<int>)':
Anna.cpp:79:8: warning: unused variable 'd' [-Wunused-variable]
   79 |    int d = getDistance(i,j, myParty ) ;
      |        ^
Anna.cpp:26:6: warning: unused variable 'lastVal' [-Wunused-variable]
   26 |  int lastVal = 0 ;
      |      ^~~~~~~

Bruno.cpp: In function 'std::vector<int> Bruno(int, std::vector<int>)':
Bruno.cpp:63:6: warning: unused variable 'x' [-Wunused-variable]
   63 |  int x = num+1 ;
      |      ^
Bruno.cpp: In lambda function:
Bruno.cpp:60:2: warning: control reaches end of non-void function [-Wreturn-type]
   60 |  } ;
      |  ^
Bruno.cpp: In function 'std::vector<int> Bruno(int, std::vector<int>)':
Bruno.cpp:53:19: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |   if( a == c && b == d ) return 4 ;
      |                 ~~^~~~
Bruno.cpp:53:9: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |   if( a == c && b == d ) return 4 ;
      |       ~~^~~~

• Subtask 1: 100 / 100