Submission #1213483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213483		repsak	Ancient Books (IOI17_books)	C++20	12 / 100	2095 ms	328 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll MAX = 1e18;

int veri(vector<int>& ajusted){
	int N = ajusted.size();
	for(int i = 0; i < N; i++){
		if(ajusted[i] != i) return 0;
	}
	
	return 1;
}

ll gen(int index, vector<int>& values, ll cost, ll& best, int holding){
	if(index < 0 || index >= values.size()) return MAX;
	if(cost >= best) return MAX;
	if(index == 0){
		if(veri(values)){
			best = min(cost, best);
			return min(cost, best);
		}
	}

	if(values[index] == -1){
		values[index] = holding;
		gen(index, values, cost, best, -1);
		values[index] = -1;
	}

	gen(index + 1, values, cost + 1, best, holding);
	gen(index - 1, values, cost + 1, best, holding);

	int valI = values[index];
	values[index] = holding;
	gen(index + 1, values, cost + 1, best, valI);
	values[index] = valI;
	
	int valE = values[index];
	values[index] = holding;
	gen(index - 1, values, cost + 1, best, valE);
	values[index] = valE;
	return best;
}

long long minimum_walk(vector<int> p, int s) {
	ll val = 16;
	return gen(0, p, 0, val, -1);
}

// #include "grader.cpp"

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