Submission #2040873


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(100*(e1 - e2) / temp)
 
 
def temperature(r):
    return 0.8 ** 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 = 48
pointmax = 48
point = 48
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 += 1
    else:
        flag = 0
if flag == 1:
    point += 1024
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 = 48
    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 += 1
        else:
            flag = 0
    if flag == 1:
        pointnext += 1024
    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]
    nowtime = datetime.now()
for i in range(V):
    print("1 {0}".format(outbest[i]))

Submission Info

Submission Time
Task A - Problem 2
User shakayami
Language PyPy3 (2.4.0)
Score 0
Code Size 2947 Byte
Status RE
Exec Time 175 ms
Memory 38640 KB

Judge Result

Set Name sample_00 sample_01 random_00 random_01 random_02 random_03 random_04 random_05 random_06 random_07 random_08 random_09 random_10 random_11 random_12 random_13 random_14 random_15 random_16 random_17 random_18 random_19 random_20 random_21 random_22 random_23 random_24 random_25 random_26 random_27
Score / Max Score 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000 0 / 1000000
Status
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
Set Name Test Cases
sample_00 00_sample_00
sample_01 00_sample_01
random_00 10_random_00
random_01 10_random_01
random_02 10_random_02
random_03 10_random_03
random_04 10_random_04
random_05 10_random_05
random_06 10_random_06
random_07 10_random_07
random_08 10_random_08
random_09 10_random_09
random_10 10_random_10
random_11 10_random_11
random_12 10_random_12
random_13 10_random_13
random_14 10_random_14
random_15 10_random_15
random_16 10_random_16
random_17 10_random_17
random_18 10_random_18
random_19 10_random_19
random_20 10_random_20
random_21 10_random_21
random_22 10_random_22
random_23 10_random_23
random_24 10_random_24
random_25 10_random_25
random_26 10_random_26
random_27 10_random_27
Case Name Status Exec Time Memory
00_sample_00 RE 172 ms 38640 KB
00_sample_01 RE 168 ms 38384 KB
10_random_00 RE 166 ms 38256 KB
10_random_01 RE 166 ms 38256 KB
10_random_02 RE 170 ms 38256 KB
10_random_03 RE 169 ms 38256 KB
10_random_04 RE 175 ms 38256 KB
10_random_05 RE 167 ms 38256 KB
10_random_06 RE 174 ms 38256 KB
10_random_07 RE 166 ms 38256 KB
10_random_08 RE 165 ms 38256 KB
10_random_09 RE 165 ms 38256 KB
10_random_10 RE 167 ms 38256 KB
10_random_11 RE 167 ms 38256 KB
10_random_12 RE 170 ms 38256 KB
10_random_13 RE 166 ms 38256 KB
10_random_14 RE 168 ms 38256 KB
10_random_15 RE 165 ms 38256 KB
10_random_16 RE 166 ms 38256 KB
10_random_17 RE 165 ms 38256 KB
10_random_18 RE 165 ms 38256 KB
10_random_19 RE 165 ms 38256 KB
10_random_20 RE 165 ms 38256 KB
10_random_21 RE 166 ms 38256 KB
10_random_22 RE 165 ms 38256 KB
10_random_23 RE 166 ms 38256 KB
10_random_24 RE 165 ms 38256 KB
10_random_25 RE 169 ms 38256 KB
10_random_26 RE 165 ms 38256 KB
10_random_27 RE 165 ms 38256 KB