Packmen

#include <algorithm>
#include <deque>
#include <iostream>
#include <string>
#include <vector>
 
using std::cin;
using std::cout;
using std::endl;
using std::vector;
 
// asume que packmen y food están ordenados y son distintos (TODOS los elementos)
bool all_eatable(const vector<int> &packmen, std::deque<int> food, int time) {
	for (int p : packmen) {
		vector<int> have_to_eat;
		while (!food.empty() && food[0] < p) {
			have_to_eat.push_back(food[0]);
			food.pop_front();
		}
 
		if (have_to_eat.empty()) {
			/*
			 * no hay que comer nada a la izquierda,
			 * así que vamos a la derecha tanto como se pueda
			 */
			while (!food.empty() && food[0] - p <= time) { food.pop_front(); }
		} else {
			if (p - have_to_eat[0] > time) {
				//  no podemos comer el pellet más a la izquierda, así que no podemos comerlos
				//  todos
				return false;
			}
 
			int left_time = p - have_to_eat[0];
			// prueba si fuimos primero a la izquierda
			int right_free_time = time - 2 * left_time;
			int left_first = -1;
			while (left_first + 1 < food.size() &&
			       food[left_first + 1] - p <= right_free_time) {
				left_first++;
			}
 
			// prueba si fuimos primero a la derecha
			right_free_time = time - left_time;
			int right_first = -1;
			while (right_first + 1 < food.size() &&
			       (food[right_first + 1] - p) * 2 <= right_free_time) {
				right_first++;
			}
 
			// nos quedamos con el máximo
			for (int i = 0; i < std::max(left_first, right_first) + 1; i++) {
				food.pop_front();
			}
		}
 
		if (food.empty()) { return true; }
	}
	return food.empty();
}
 
int main() {
	int field_len;
	cin >> field_len;
	std::string field;
	cin >> field;
	for (char &c : field) { c = toupper(c); }
 
	vector<int> packmen;
	std::deque<int> food;
	for (int i = 0; i < field.length(); i++) {
		if (field[i] == 'P') {
			packmen.push_back(i);
		} else if (field[i] == '*') {
			food.push_back(i);
		}
	}
 
	int lo = 0;
	int hi = field.length() * 2;
	int valid = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (all_eatable(packmen, food, mid)) {
			valid = mid;
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}
 
	cout << valid << endl;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Packmen {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		read.readLine();
		char[] field = read.readLine().toUpperCase().toCharArray();
		ArrayList<Integer> packmen = new ArrayList<>();
		ArrayList<Integer> food = new ArrayList<>();
		for (int i = 0; i < field.length; i++) {
			if (field[i] == 'P') {
				packmen.add(i);
			} else if (field[i] == '*') {
				food.add(i);
			}
		}
 
		int lo = 0;
		int hi = field.length * 2;
		int valid = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			if (allEatable(packmen, food, mid)) {
				valid = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
 
		System.out.println(valid);
	}
 
	// asume que todo está ordenado y es distinto
	private static boolean allEatable(ArrayList<Integer> packmen,
	                                  ArrayList<Integer> food, int time) {
		/*
		 * como los deques de Java no permiten indexar, mantenemos un
		 * puntero al pellet no comido más a la izquierda y lo movemos en consecuencia
		 */
		int foodPointer = 0;
		int foodAmt = food.size();  // atajo
		for (int p : packmen) {
			ArrayList<Integer> haveToEat = new ArrayList<>();
			while (foodPointer < foodAmt && food.get(foodPointer) < p) {
				haveToEat.add(food.get(foodPointer++));
			}
 
			if (haveToEat.isEmpty()) {
				/*
				 * no hay que comer nada a la izquierda,
				 * así que vamos a la derecha tanto como se pueda
				 */
				while (foodPointer < foodAmt && food.get(foodPointer) - p <= time) {
					foodPointer++;
				}
			} else {
				// no podemos comer el pellet más a la izquierda, así que no podemos comerlos todos
				if (p - haveToEat.get(0) > time) { return false; }
				int leftTime = p - haveToEat.get(0);
				// probamos ir primero a la izquierda y luego a la derecha
				int rightFreeTime = time - 2 * leftTime;
				int leftFirst = -1;
				while (foodPointer + leftFirst + 1 < foodAmt &&
				       food.get(foodPointer + leftFirst + 1) - p <= rightFreeTime) {
					leftFirst++;
				}
 
				// probamos ir primero a la izquierda
				rightFreeTime = time - leftTime;
				int rightFirst = -1;
				while (foodPointer + rightFirst + 1 < foodAmt &&
				       2 * (food.get(foodPointer + rightFirst + 1) - p) <=
				           rightFreeTime) {
					rightFirst++;
				}
 
				foodPointer += Math.max(leftFirst, rightFirst) + 1;
			}
			if (foodPointer >= foodAmt) { return true; }
		}
		return foodPointer >= foodAmt;
	}
}

from typing import List
 
 
def eatable_in_time(food: List[int], packmen: List[int], time: int) -> bool:
	"""asume que las posiciones están ordenadas y son distintas"""
	food_pointer = 0
	food_amt = len(food)  # atajo conveniente
	for p in packmen:
		have_to_eat = []
		# asignamos a este packman todos los de su izquierda que no se hayan comido
		while food_pointer < food_amt and food[food_pointer] < p:
			have_to_eat.append(food[food_pointer])
			food_pointer += 1
 
		if not have_to_eat:
			while food_pointer < food_amt and food[food_pointer] - p <= time:
				food_pointer += 1
 
		else:
			# no podemos comer todos los pellets si no podemos comer el más a la izquierda
			if p - have_to_eat[0] > time:
				return False
 
			# vamos a la izquierda o a la derecha, y luego volvemos
			left_time = p - have_to_eat[0]
			right_free_time = time - 2 * left_time
			left_first = -1
			while (
				food_pointer + left_first + 1 < food_amt
				and food[food_pointer + left_first + 1] - p <= right_free_time
			):
				left_first += 1
 
			right_free_time = time - left_time
			right_first = -1
			while (
				food_pointer + right_first + 1 < food_amt
				and 2 * (food[food_pointer + right_first + 1] - p) <= right_free_time
			):
				right_first += 1
			food_pointer += max(left_first, right_first) + 1
 
		if food_pointer >= food_amt:  # ok, se comió toda la comida
			return True
	return food_pointer >= food_amt
 
 
input()
field = input().upper()
 
all_food = []
all_packmen = []
for v, c in enumerate(field):
	if c == "P":
		all_packmen.append(v)
	elif c == "*":
		all_food.append(v)
 
lo = 0
hi = len(field) * 2
valid = -1
while lo <= hi:
	mid = (lo + hi) // 2
	if eatable_in_time(all_food, all_packmen, mid):
		valid = mid
		hi = mid - 1
	else:
		lo = mid + 1
 
print(valid)