m00nlight

from Queue import Queue
from threading import Thread
from random import randrange

queue = Queue(10)

class Consumer(Thread):
    def __init__(self, queue):
        Thread.__init__(self)
        self.queue = queue

m00nlight

def lower_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) / 2
        if nums[mid] >= target:
            r = mid - 1
        else:
            l = mid + 1
    return l
    

m00nlight

import sys
from heapq import heappush, heappop

class UFSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]
        
    def find(self, v):
        if v != self.fa[v]:
            self.fa[v] = self.find(self.fa[v])

m00nlight

import sys
import itertools

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    

m00nlight

import sys
import itertools

def extend_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        (a1, b1, g) = extend_gcd(b, a % b)
        return (b1, a1 - (a // b) * b1, g)
    

m00nlight

import sys
import itertools

class RMQ:
    def __init__(self, n):
        self.sz = 1
        self.inf = (1 << 31) - 1
        while self.sz <= n: self.sz = self.sz << 1
        self.dat = [self.inf] * (2 * self.sz - 1)
    

m00nlight

from operator import add, sub
import sys

def max_subarray(arr):
    ret, cur = arr[0], 0 if arr[0] < 0 else arr[0]
    
    for num in arr[1:]:
        ret = max(ret, cur + num)
        cur = max(0, cur + num)
    return ret

m00nlight

import random

def merge_sort(xs):
    """Inplace merge sort of array without recursive. The basic idea
    is to avoid the recursive call while using iterative solution. 
    The algorithm first merge chunk of length of 2, then merge chunks
    of length 4, then 8, 16, .... , until 2^k where 2^k is large than 
    the length of the array
    """
    

m00nlight

import operator

Symbol = str

def tokenize(exp):
    return exp.replace('(', ' ( ').replace(')', ' ) ').split()
    
def parser(exp):
    return read_from_tokens(tokenize(exp))
    

m00nlight

#!/usr/local/Gambit-C/bin/gsi

; Copyright (C) 2004 by Marc Feeley, All Rights Reserved.

; This is the "90 minute Scheme to C compiler" presented at the
; Montreal Scheme/Lisp User Group on October 20, 2004.

; Usage with Gambit-C 4.0:
;
;    % ./90-min-scc.scm test.scm