Submission #137395

#	Time	Username	Problem	Language	Result	Execution time	Memory
137395		wilwxk	Ancient Books (IOI17_books)	C++14	12 / 100	2045 ms	380 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 respf, ciclos;

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

	int mao=v[atual];
	v[atual]=-1;
	while(mao!=-1) {
		respf+=abs(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&&v[atual]==atual) atual++, respf++;
	while(bons<n) melhora(), ciclos++;
	respf+=abs(atual-ori);

	// printf("%lld // %d\n", respf, ciclos);
	respf-=max(0LL, (ciclos-1));
	return respf;
}

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