Submission #69284174

---

Source Code Expand

import bisect, heapq, sys, math, copy, itertools, decimal
from collections import defaultdict, deque
import pprint
import random
random.seed(1234)
sys.setrecursionlimit(10**7)
def INT(): return int(input())
def MI(d=0): return map(lambda x:int(x)+d, input().split())
def MS(): return map(str, input().split())
def LI(d=0): return list(map(lambda x:int(x)+d, input().split()))
def LS(): return list(map(str, input().split()))
def pr_line(itr): print(*itr, sep='\n')
def pr_mtx(matrix): [print(*row) for row in matrix] 
def pr_mtx2(matrix, l=2):
    for row in matrix:
        for x in row:
            print(str(x).rjust(l), end='')
        print('\n')
def pr_stderr(*s): print(*s, file=sys.stderr)

dij = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dij2 = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
INF = float('inf')


from time import time
base_ms = 0
def tic():
    global base_ms
    base_ms = time()

def toc():
    now = time()
    return (now - base_ms) * 1000
###########################################################

def log_uniform(low, high, base=10):
    log_low = math.log(low, base)
    log_high = math.log(high, base)
    r = random.uniform(log_low, log_high)
    return int(base ** r)

N, M, L, U = MI()

A = [10**15 - 2*10**12]*50 + [random.randint(8*10**9, 5*10**11) for _ in range(N-M)]

# A = [10**15 - 2*10**12]*50 + \
#     [random.randint(10**11, 10**12) for _ in range(350)] + \
#     [random.randint(10**9, 10**10) for _ in range(100)] 

print(*A)

B = LI()

def init_sol():
    S = [0]*M
    X = [0]*N

    cards = sorted(enumerate(A), key=lambda x: -x[1])

    for idx, val in cards:
        best_increase = None
        best_j = 0
        for j in range(M):
            old_cost = abs(S[j]-B[j])
            new_cost = abs(S[j]+val-B[j])
            increase = new_cost - old_cost
            if best_increase is None or increase < best_increase:
                best_increase = increase
                best_j = j+1
        if best_increase > 0 and random.random() < 0.2:
            X[idx] = 0
        else:
            X[idx] = best_j
            S[best_j-1] += val
    
    return X, S

def cost(S, B):
    return sum(abs(S[i]-B[i]) for i in range(M))

def annealing(X, S):
    def multi_update(idxs, new_groups, cur_X, cur_S, cur_cost):
        changed = []       
        new_cost = cur_cost

        for idx, new_group in zip(idxs, new_groups):
            old_group = cur_X[idx]
            if new_group == old_group:
                continue

            val = A[idx]
            # old_group の更新
            if old_group != 0:
                j = old_group - 1
                new_cost -= abs(cur_S[j] - B[j])
                cur_S[j] -= val
                new_cost += abs(cur_S[j] - B[j])

            # new_group の更新
            if new_group != 0:
                j = new_group - 1
                new_cost -= abs(cur_S[j] - B[j])
                cur_S[j] += val
                new_cost += abs(cur_S[j] - B[j])

            # 差分記録
            changed.append((idx, old_group, new_group, val))

        return new_cost, cur_S, changed

    best_X = X[:]
    best_S = S[:]
    best_cost = cost(S, B)

    cur_X = X[:]
    cur_S = S[:]
    cur_cost = best_cost

    start_time = time()
    TIME_LIMIT = 1.7

    T0 = 1000   
    T_end = 1e-2 

    iters = 0
    adapted = 0
    while time() - start_time < TIME_LIMIT:
        iters += 1
        progress = (time()-start_time) / TIME_LIMIT
        T = T0 * (T_end / T0) ** progress
        
        k = 2
        idxs = random.sample(range(N), k)
        new_groups = [random.randint(0, M) for _ in range(len(idxs))]

        new_cost, cur_S, changed = multi_update(idxs, new_groups, cur_X, cur_S, cur_cost)
        if not changed:
            continue

        diff = new_cost - cur_cost
        if diff < 0 or random.random() < math.exp(-diff / T):
            adapted += 1
            for idx, old_g, new_g, _ in changed:
                cur_X[idx] = new_g
            cur_cost = new_cost
            if new_cost < best_cost:
                best_cost = new_cost
                best_X = cur_X[:]
                best_S = cur_S[:]
        else:
            for idx, old_g, new_g, val in changed:
                if new_g != 0:
                    j = new_g - 1
                    cur_S[j] -= val
                if old_g != 0:
                    j = old_g - 1
                    cur_S[j] += val
            cur_cost = cur_cost
        
        #pr_stderr(best_cost)
    pr_stderr(iters, adapted, best_cost)
    return best_X, best_S, best_cost

X, S = init_sol()

X, S, cost = annealing(X, S)

un_use = []
d = defaultdict(int)
for i, x in enumerate(X):
    if x == 0:
        un_use.append(len(str(A[i])))
    d[len(str(A[i]))] += 1

pr_stderr(*un_use)
pr_stderr(d)

print(*X)

Submission Info

Judge Result