Submission #2326032

---

Source Code Expand

import math
import numpy
import random
from datetime import datetime


def coord(n, x, y):
    return int(x + n * y + 1)


def probability(e1, e2, temp):
    if (e1 >= e2):
        return 1
    else:
        return math.exp((e1 - e2) / temp)


def temperature(r):
    return 0.8101919 ** r


start = datetime.now()
s = input().split()
V = int(s[0]);
E = int(s[1])
u = [0 for i in range(E)]
v = [0 for i in range(E)]
mat = [[0 for i in range(V)] for i in range(V)]
node = [0 for i in range(V)]
for i in range(E):
    s = input().split()
    u[i] = int(s[0]) - 1;
    v[i] = int(s[1]) - 1
    node[u[i]] += 1
    node[v[i]] += 1
ns = list(numpy.argsort(numpy.array(node)))
s = input().split()
Vemb = int(s[0]);
Eemb = int(s[1])
for i in range(Eemb):
    st = input()
out = [0 for i in range(V)]
outtemp = [0 for i in range(V)]
outbest = [0 for i in range(V)]
n = int(math.sqrt(Vemb))
i = n // 2 - 1
j = n // 2 - 1
di = 1
dj = 0
m = 1
for k in range(V):
    out[V - 1 - ns[k]]=(coord(n, i, j))
    outtemp[V - 1 - ns[k]]=(coord(n, i, j))
    outbest[V - 1 - ns[k]]=(coord(n, i, j))
    if (m * m + 1 == k + 1):
        dj = (m % 2) * 2 - 1
        di = 0
        m += 1
    elif (m * m - m + 1 == k + 1):
        di = (m % 2) * 2 - 1
        dj = 0
    i += di
    j += dj
nowtime = datetime.now()
pointnext = 5000
pointmax = 5000
point = 5000
flag = 1
for i in range(E):
    j = out[u[i]]
    k = out[v[i]]
    jx = j % n
    jy = j // n
    kx = k % n
    ky = k // n
    dx = jx - kx;
    dy = jy - ky
    if (dx == -1 or dx == 0 or dx == 1) and (dy == -1 or dy == 0 or dy == 1):
        point += 100
    else:
        flag = 0
if flag == 1:
    point += 100000
while ((nowtime - start).total_seconds() < 29):
    time = (nowtime - start).total_seconds() / 29
    p = random.randrange(V)
    q = random.randrange(V)
    if (p == q):
        while (1 == 1):
            p = random.randrange(V)
            q = random.randrange(V)
            if (p != q):
                break
    outpq = outtemp[p]
    outtemp[p]=outtemp[q]
    outtemp[q]=outpq
    pointnext = 5000
    flag = 1
    for i in range(E):
        j = outtemp[u[i]]
        k = outtemp[v[i]]
        jx = j % n
        jy = j // n
        kx = k % n
        ky = k // n
        dx = jx - kx;
        dy = jy - ky
        if (dx == -1 or dx == 0 or dx == 1) and (dy == -1 or dy == 0 or dy == 1):
             pointnext += 100
        else:
            flag = 0
    if flag == 1:
        pointnext += 100000
    if (pointmax < pointnext):
        for i in range(V):
            outbest[i]=outtemp[i]
        pointmax = pointnext
    if random.random() <= probability(pointnext, point, temperature(time)):
        point = pointnext
        for i in range(V):
            out[i]=outtemp[i]
    for i in range(V):
        outtemp[i]=out[i]
    nowtime = datetime.now()
for i in range(V):
    print("1 {0}".format(outbest[i]))

Submission Info

Judge Result