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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |