fork download
copy 
  1. def solve(k, s, p):
  2.   seat1 = s[0]
  3.   best = -1
  4.   unlucky = (0, -1) # min(accum), position
  5.   accum = 1
  6.  
  7.   # process all persons between start of the array and the seat #1 position
  8.   for i, pos in enumerate(p):
  9.     if pos <= seat1:
  10.       best = i+1
  11.       accum -= 1
  12.     else:
  13.       break
  14.  
  15.   if accum < 0:
  16.     unlucky = (accum, 1)
  17.  
  18.   # process all seats/persons in reverse direction
  19.   i = k
  20.   j = k-1
  21.   while i >= 0 and p[i] > seat1:
  22.     if s[j] >= p[i]: # a seat
  23.       accum += 1
  24.       j -= 1
  25.     else: # a person
  26.       accum -= 1
  27.       i -= 1
  28.  
  29.     if best == -1 and accum == 0:
  30.       best = i+2 # +1 because indexing starts with 0 & +1 because of pre-decrement
  31.  
  32.     if accum < unlucky[0]:
  33.       unlucky = (accum, i+2)
  34.  
  35.   return (best, unlucky[1])
  36.  
  37.  
  38. print(solve(3, [2,5,8], [3,4,6,8]))
  39.  
Success #stdin #stdout 0.08s 8832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(3, 1)
https://ideone.com/oAeFYY
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!