Submission #600837

#	Time	Username	Problem	Language	Result	Execution time	Memory
600837		Lucpp	Ancient Books (IOI17_books)	C++17	0 / 100	2077 ms	212 KiB

books

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

long long minimum_walk(vector<int> p, int s){
	int n = (int)p.size();
	ll ans = 0;
	vector<bool> vis(n);
	int mi = s, ma = s;
	int l = s, r = s;
	while(true){
		int i = -1;
		while(r <= ma){
			if(!vis[r]){
				i = r;
				break;
			}
			r++;
		}
		if(i != -1)
		while(l >= mi){
			if(!vis[l]){
				i = l;
				break;
			}
			l--; 
		}
		if(i == -1){
			int oldR = r, oldL = l;
			while(r < n){
				if(p[r] != r){
					i = r;
					ans += 2*(r+1-oldR);
					break;
				}
				r++;
			}
			if(i == -1)
			while(l >= 0){
				if(p[l] != l){
					i = l;
					ans += 2*(oldL+1-l);
					break;
				}
				l--;
			}
			if(i == -1) break;
		}
		int j = i;
		do
		{
			vis[j] = true;
			mi = min(mi, p[j]);
			ma = max(ma, p[j]);
			ans += abs(j-p[j]);
			j = p[j];
		}while(j != i);
	}
	return ans;
}

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