Submission #1124549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124549		NotLinux	Ancient Books (IOI17_books)	C++20	50 / 100	116 ms	19944 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long minimum_walk(vector<int> p, int s) {
	int n = (int)p.size();
	int ans[n-1]={0} , pre1[n-1]={0} , pre2[n-1]={0};
	for(int i = 0;i<n;i++){
		if(p[i] > i){
			pre1[i]++;
			pre1[p[i]]--;
		}
		else if(p[i] < i){
			pre2[i]--;
			pre2[p[i]]++;
		}
	}
	for(int i = 0;i<n-1;i++){
		if(i > 0){
			pre1[i] += pre1[i-1];
			pre2[i] += pre2[i-1];
		}
		// cout << i << " : " << pre1[i] << " , " << pre2[i] << endl;
		ans[i] = max(pre1[i] , pre2[i]) * 2;
	}
	bool bl = 0;
	for(int i = 0;i<s;i++){
		if(ans[i]){
			bl = 1;
		}
		else if(ans[i] == 0 and bl){
			ans[i] = 2;
		}
	}
	bl = 0;
	for(int i = n-2;i>=s;i--){
		if(ans[i]){
			bl = 1;
		}
		else if(ans[i] == 0 and bl){
			ans[i] = 2;
		}
	}
	long long ret = 0;
	for(int i = 0;i<n-1;i++)ret += ans[i];
	return ret;
}

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