Участник:Toxandr17/serejaandshuffling

Материал из DISCOPAL
Перейти к: навигация, поиск

Task: https://www.codechef.com/problems/SEASHUF

from random import random
from _bisect import bisect_right
 
class ShufflerGenome(object):
	def __init__(self, a, lsum, rsum):
		self.array = a[:]
		self.shuffles = []
		self._left = 2*n
		self._lsum = lsum
		self._rsum = rsum
		self._initWithRandomShuffles()
 
	def _initWithRandomShuffles(self):
		while True:
			u = int(random()*halfn)
			v = halfn + int(random()*halfn1)
			if (v - u + 1 > self._left): break
			self._left -= v - u + 1
			self.shuffles.append((u, v))
			self.shuffle(u, v)
 
	def shuffle(self, l, r):
		""" Сдвигает  подмассив массива в пределах [l..r]
			Например: Измененный массив [1 2 3 4 5 6] в пределах [2..4]
				будет выглядеть так: [1 3 4 2 5 6]"""
		self._lsum -= self.array[l]
		self._lsum += self.array[halfn]
		self._rsum -= self.array[halfn]
		self._rsum += self.array[l]
		p = self.array[l]
		for i in range(l, r):
			self.array[i] = self.array[i+1]
		self.array[r] = p
 
	def unshuffle(self, l, r):
		""" Возвращает исходный массив
			Пример:  [1 3 4 2 5 6] в пределах [2..4]
				будет выглядеть [1 2 3 4 5 6]"""
		self._lsum += self.array[r]
		self._lsum -= self.array[halfn-1]
		self._rsum += self.array[halfn-1]
		self._rsum -= self.array[r]
		p = self.array[r]
		for i in range(r, l, -1):
			self.array[i] = self.array[i-1]
		self.array[l] = p
 
	def getCost(self):
		""" Возвращает модуль разности  сумм левой и правой части массива """
		return abs(self._lsum - self._rsum)
 
	def mutate(self, gene):
		self._left += self.shuffles[gene][1] - self.shuffles[gene][0] + 1
		u = int(random()*halfn)
		v = halfn + int(random()*halfn1)
		if (v - u + 1 > self._left): self.shuffles.pop(gene)
		else:
			self._left -= v - u + 1
			self.shuffles[gene] = (u, v)
			for i in range(len(self.shuffles)-1, gene, -1):
				self.unshuffle(*self.shuffles[i])
			for i in range(gene, len(self.shuffles)):
				self.shuffle(*self.shuffles[i])
 
	def print_shuffles(self):
		print(len(self.shuffles))
		for i in self.shuffles:
			print(i[0]+1, i[1]+1)
 
	def __str__(self):
		out = ""
		out += "[Cost: %d\tLeft:%d\tSwaps: %d] " % (self.getCost(), self._left, len(self.shuffles))
		for i in self.array: out += str(i) + " "
		return out
 
if __name__ == '__main__':
	global a, n, halfn, halfn1
	n = int(input())
	a = [int(i) for i in input().split()]
	halfn = n >> 1
	halfn1 = (n+1) >> 1
	lsum = sum(a[:halfn])
	rsum = sum(a[halfn:])
 
	population = 100
	mutationrate = 0.015
	generation = 1
	jarray = [ShufflerGenome(a, lsum, rsum) for i in range(population)]
	jarray.sort(key=lambda x: x.getCost())
	# print(candidates[0])
	jarray[0].print_shuffles()