Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <concurrent_priority_queue.h>

#define RC2P(r,c) (((r)<<2)+(c))	//r*4+c
#define P2R(p) ((p)>>2)				//p/4
#define P2C(p) ((p)&3)				//p%4
#define HASHMAX 1000003

typedef unsigned long long int Pkey;

struct Pandt{
	Pkey p;
	int t;

	Pandt(){ return; }
	Pandt(Pkey p, int t) :p(p), t(t){ return; }

	bool operator==(const Pandt& rhs) const{
		return (p == rhs.p && t == rhs.t);
	}
};

int dist(Pkey x);
int abs(int x);
void insert(std::vector<Pkey> &A, Pkey v);
Pkey extract(std::vector<Pkey> &A);
int SolvePuzzle(std::vector<int> P);


std::vector< Pandt > Puzzles(HASHMAX);

int h1(Pkey key){
	return (int)(key % HASHMAX); 
}
int h2(Pkey key){
	return (int)((key % (HASHMAX - 1)) + 1);
}
int HashFind(Pkey key);
int HashInsert(Pkey key, int val);


void InitHash(){
	Pandt Nullpandt(0, -1);
	for (int i = 0; i < HASHMAX; i++){
		Puzzles[i] = Nullpandt;
	}
}

int HashFind(Pkey key){

	int curhash = h1(key);
	int sechash = h2(key);
	for (int i = 0; i < HASHMAX; i++){
		if (Puzzles[curhash].p == key && Puzzles[curhash].t != -1){
			return curhash;
		}
		else if (Puzzles[curhash].t == -1){
			return -1;
		}
		else{
			curhash = (curhash + sechash) % HASHMAX;
		}
	}
	return -1;
}

int HashInsert(Pkey key, int val){

	int curhash = h1(key);
	int sechash = h2(key);
	for (int i = 0; i < HASHMAX; i++){
		if (Puzzles[curhash].t == -1){
			Puzzles[curhash].t = val;
			Puzzles[curhash].p = key;
			return curhash;
		}
		else{
			curhash = (curhash + sechash) % HASHMAX;
		}
	}
	return -1;
}

void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
	return;
}

int dist(Pkey x){
	int tmp, result = 0;
	for (int i = 0; i < 16; i++){
		tmp = (x & ((Pkey)15 << (i << 2))) >> (i << 2);
		if (tmp == 0) continue;
		result += abs(P2C(tmp - 1) - P2C(i)) + abs(P2R(tmp - 1) - P2R(i));
	}
	int s = HashFind(x);
	return -result - (s == -1 ? 1048576 : Puzzles[s].t);
}

int abs(int x){
	return x < 0 ? -x : x;
}

void insert(std::vector< Pkey > &A, Pkey v){
	int n = A.size();
	A.push_back(v);
	while (n != 0){
		int i = (n - 1) >> 1;
		if (dist(A[n]) > dist(A[i])){
			Pkey tmp = A[n];
			A[n] = A[i];
			A[i] = tmp;
		}
		n = i;
	}
	return;
}

Pkey extract(std::vector< Pkey > &A){
	int n = A.size() - 1;
	Pkey res = A[0];
	A[0] = A[n];
	A.pop_back();

	for (int i = 0, j; 2 * i + 1 < n;){
		j = 2 * i + 1;
		if (j != n - 1 && dist(A[j]) < dist(A[j + 1])){
			j++;
		}
		if (dist(A[i]) < dist(A[j])){
			Pkey tmp = A[j];
			A[j] = A[i];
			A[i] = tmp;
		}
		i = j;
	}
	return res;
}

Pkey PtoI(std::vector<int> p){
	unsigned long long int keyI = 0;
	for (int i = 0; i < 16; i++){
		keyI += (unsigned long long int)(15 & p[i]) << (i << 2);
	}
	return keyI;
}

int SolvePuzzle(std::vector<int> P){
	std::vector< Pkey > Que;
	Pkey init = PtoI(P);
	HashInsert(init, 0);
	insert(Que, init);
	int answer = 10000;
	while (!Que.empty()){
		Pkey extp = extract(Que);
		int extt = Puzzles[HashFind(extp)].t;
		int Cursor;
		bool isAligned = (extp == 0xFEDCBA987654321);
		if (isAligned){
			answer = extt;
			break;
		}

		if (-dist(extp) >= 45) continue;

		for (int i = 0; i < 16; i++){
			if ((extp & ((Pkey)15 << (i << 2))) == 0){
				Cursor = i;
				break;
			}
		}
		Pkey Qnext;
		int Qsearch;
		Pkey tmp;
		if (Cursor >= 4){
			tmp = (extp & ((Pkey)15 << ((Cursor - 4) << 2)));
			Qnext = extp & ~tmp | (tmp << 16);
			Qsearch = HashFind(Qnext);
			if (Qsearch == -1){
				HashInsert(Qnext, extt + 1);
				insert(Que, Qnext);
			}
			else if (Puzzles[Qsearch].t > extt + 1){
				Puzzles[Qsearch].t = extt + 1;
				insert(Que, Qnext);
			}
		}
		if (Cursor < 12){
			tmp = (extp & ((Pkey)15 << ((Cursor + 4) << 2)));
			Qnext = extp & ~tmp | (tmp >> 16);
			Qsearch = HashFind(Qnext);
			if (Qsearch == -1){
				HashInsert(Qnext, extt + 1);
				insert(Que, Qnext);
			}
			else if (Puzzles[Qsearch].t > extt + 1){
				Puzzles[Qsearch].t = extt + 1;
				insert(Que, Qnext);
			}
		}
		if (P2C(Cursor) != 0){
			tmp = (extp & ((Pkey)15 << ((Cursor - 1) << 2)));
			Qnext = extp & ~tmp | (tmp << 4);
			Qsearch = HashFind(Qnext);
			if (Qsearch == -1){
				HashInsert(Qnext, extt + 1);
				insert(Que, Qnext);
			}
			else if (Puzzles[Qsearch].t > extt + 1){
				Puzzles[Qsearch].t = extt + 1;
				insert(Que, Qnext);
			}
		}
		if (P2C(Cursor) != 3){
			tmp = (extp & ((Pkey)15 << ((Cursor + 1) << 2)));
			Qnext = extp & ~tmp | (tmp >> 4);
			Qsearch = HashFind(Qnext);
			if (Qsearch == -1){
				HashInsert(Qnext, extt + 1);
				insert(Que, Qnext);
			}
			else if (Puzzles[Qsearch].t > extt + 1){
				Puzzles[Qsearch].t = extt + 1;
				insert(Que, Qnext);
			}
		}
	}

	return answer;
}

int main(){

	InitHash();

	int k;
	std::vector<int> P;
	for (int i = 0; i < 16; i++){
		scanf("%d", &k);
		P.push_back(k);
	}
	int n = SolvePuzzle(P);

	printf("%d\n", n);

	return 0;
}


Compiler output:
a.cc:4:10: fatal error: concurrent_priority_queue.h: No such file or directory
    4 | #include <concurrent_priority_queue.h>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.