Submission #1233095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233095		Gabriel	Ancient Books (IOI17_books)	C++20	0 / 100	2098 ms	120992 KiB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;
int n;
struct No_repetir{
	vector<int> p;
	int Inicio, Posici_n, Mano;
};
bool operator<(const No_repetir& a, const No_repetir& b){
	if(a.p < b.p) return 1;
	if(a.p > b.p) return 0;
	if(a.Inicio < b.Inicio) return 1;
	if(a.Inicio > b.Inicio) return 0;
	if(a.Posici_n < b.Posici_n) return 1;
	if(a.Posici_n > b.Posici_n) return 0;
	return a.Mano < b.Mano;
}
map<No_repetir, long long> Programaci_n_din_mica_que_parece_recursi_n;
set<No_repetir> No;
long long Resolver(vector<int> p, int Inicio, int Posici_n, int Mano){
	/*for(auto E: p) cerr<<E<<" ";
	cerr<<"\n"<<Inicio<<" "<<Posici_n<<" "<<Mano<<"\n";*/
	bool Bien = 1;
	for(int i = 0; i < n and Bien; i++) if(p[i] != i) Bien = 0;
	if(Bien) return abs(Posici_n - Inicio);
	No_repetir Estado;
	Estado.Inicio = Inicio;
	Estado.Mano = Mano;
	Estado.p = p;
	Estado.Posici_n = Posici_n;
	if(Programaci_n_din_mica_que_parece_recursi_n.count(Estado) == 1) return Programaci_n_din_mica_que_parece_recursi_n.count(Estado);
	if(No.count(Estado) == 1) return 2222222222222222;
	No.insert(Estado);
	long long r = 2222222222222222;
	if(Mano == -2){
		for(int i = 0; i < n; i++){
			swap(Mano, p[i]);
			r = min(r, Resolver(p, Inicio, i, Mano) + abs(i - Posici_n));
			swap(Mano, p[i]);
		}
	} else {
		int Ir = Mano;
		swap(p[Mano], Mano);
		r = min(r, Resolver(p, Inicio, Ir, Mano) + abs(Ir - Posici_n));
	}
	No.erase(Estado);
	if(No.empty()) return Programaci_n_din_mica_que_parece_recursi_n[Estado] = r;
	else return r;
}
long long minimum_walk(vector<int> p, int s){
	n = p.size();
	return Resolver(p, s, 0, -2);
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30