Submission #137382

#	Time	Username	Problem	Language	Result	Execution time	Memory
137382		wilwxk	Ancient Books (IOI17_books)	C++14	12 / 100	2044 ms	464 KiB

books

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

const int MAXN=1e6+6;
vector<int> v;
int n, ori, atual, bons;
ll vai, respf;

bool melhora() {
	if(atual>=n) return 0;
	while(bons<n&&v[atual]==atual) respf++, atual++;
	// printf("atual %d\n", atual);

	int mao=v[atual];
	v[atual]=-1;
	while(mao!=-1) {
		respf+=abs(mao-atual);
		if(mao-atual>0) vai+=(mao-atual);
		atual=mao;
		swap(mao, v[atual]);
		if(v[atual]==atual) bons++;
	}
	// for(auto cur : v) printf("%d ", cur);
	// printf(" >> %lld // %d\n", respf, atual);
	return 1;
}

long long minimum_walk(std::vector<int> P, int S) {
	n=P.size(); v=P; ori=S; atual=ori;
	for(int i=0; i<n; i++) if(v[i]==i) bons++;

	while(bons<n) melhora();
	respf+=abs(atual-ori);

	ll volta=respf-vai;
	respf=min(respf, min(vai, (ll)n)+volta);
	respf=min(respf, min(volta, (ll)n)+vai);
	return respf;
}

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