Submission #20464056

---

Source Code Expand

#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True
from __future__ import print_function
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from decimal import *
from heapq import heapify, heappop, heappush
from time import time, sleep
from random import randint, random
def debug(*args): print(*args, file=sys.stderr)
cdef input(): return sys.stdin.readline().strip()
cdef STR(): return input()
cdef int INT(): return int(input())
cdef double FLOAT(): return double(input())
cdef MAP(): return map(int, input().split())
cdef S_MAP(): return map(str, input().split())
cdef LIST(): return list(map(int, input().split()))
cdef S_LIST(): return list(map(str, input().split()))
cdef int lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
cdef int inf = 2 * 10 ** 9
cdef int mod = 10 ** 9 + 7
cdef int[8] dx = [0, 1, 0, -1, 1, -1, -1, 1]
cdef int[8] dy = [1, 0, -1, 0, 1, -1, 1, -1]

cdef double start_temp = 20
cdef double end_tmp = 5

cdef double tempera(double strt, double now, double tl):
    return start_temp + (end_tmp - start_temp) * (now - strt) / tl

cdef double prob(int p_score, int n_score, double strt, double now, double tl):
    cdef double dis = n_score - p_score
    if dis >= 0:
        return 1.0
    return pow(2, dis / tempera(strt, now, tl))


cdef int proc_x(x):
    if x > n:
        return 2 * n - x
    elif x < 0:
        return n + x
    return x

cdef double max_plus(int x, int num_1, int dice3, int dice4):
    cdef int i
    cdef double res
    res = 0.0
    for i in [num_1 - 1, num_1 + 1]:
        if 0 <= i <= 4:
            res = max(res, data[x][i][dice3 - 1][dice4 - 1])
    res = max(res, max(data[x][num_1][i][dice4 - 1] for i in range(6)), max(data[x][num_1][dice3 - 1][i] for i in range(6)))
    return res

cdef void proc_point():
    global points
    cdef int x, nx, end
    cdef double tmp
    for x in range(n):
        if points[x] == -1:
            tmp = 0
            for nx in reversed(range(x)):
                if points[nx] != -1:
                    tmp += points[nx]
                    break
            for nx in range(x + 1, n):
                if points[nx] != -1:
                    tmp += points[nx]
                    break
            points[x] = tmp / 2
    x = 0
    while x < n:
        if points[x] > 0:
            for nx in range(x + 1, n):
                if points[nx] > 0:
                    end = nx
                    break
            else:
                end = n
            for nx in range(x, end):
                points[nx] += (end - nx) * 0.75
                #if 100 < nx < 400:
                #    points[nx] *= 1.05
            x = end
        else:
            x += 1

cdef void init_data():
    global data
    cdef int x, num_1, num_6, dice3, dice4
    for x in range(n + 1):
        for num_1 in range(5):
            for dice3 in range(1, 7):
                for dice4 in range(1, 7):
                    if x == n:
                        data[x][num_1][dice3 - 1][dice4 - 1] = 5000.0
                    else:
                        data[x][num_1][dice3 - 1][dice4 - 1] = 0.0
                    
    for _ in range(2):
        for x in reversed(range(n)):
            for num_1 in range(5):
                for dice3 in range(1, 7):
                    for dice4 in range(1, 7):
                        data[x][num_1][dice3 - 1][dice4 - 1] = points[x]
                        data[x][num_1][dice3 - 1][dice4 - 1] += max_plus(proc_x(x + 1), num_1, dice3, dice4) * num_1 / 6
                        data[x][num_1][dice3 - 1][dice4 - 1] += max_plus(proc_x(x + 6), num_1, dice3, dice4) * (4 - num_1) / 6
                        data[x][num_1][dice3 - 1][dice4 - 1] += max_plus(proc_x(x + dice3), num_1, dice3, dice4) / 6
                        data[x][num_1][dice3 - 1][dice4 - 1] += max_plus(proc_x(x + dice4), num_1, dice3, dice4) / 6
                        data[x][num_1][dice3 - 1][dice4 - 1] -= 200.0
                        if x + 6 > n:
                            data[x][num_1][dice3 - 1][dice4 - 1] -= 10
                        if x + dice3 > n:
                            data[x][num_1][dice3 - 1][dice4 - 1] -= 10
                        if x + dice4 > n:
                            data[x][num_1][dice3 - 1][dice4 - 1] -= 10

cdef int n, m, score
cdef int[6] n_dice, f_dice
cdef double[501] points
cdef double[501][5][6][6] data
cdef int max_inf_idx = 8
cdef int small_inf = 10000
cdef int end_dice = 6
cdef int threshold = 50

cdef main():
    global n, m, n_dice, f_dice, points, score
    n, m = MAP()
    cdef double all_strt = time()
    cdef int turn, d, v, x, idx, idx2, target, target_idx, num_1, p_num_1, n_num_1, change_idx, fix_idx, dice3, dice4, n_dice3, n_dice4
    cdef double point, max_point
    n_dice = [1, 2, 3, 4, 5, 6]
    for idx in range(n + 1):
        points[idx] = -1
    points[n] = 5000
    
    score = 0
    x = 0
    turn = 0
    target = 3
    while True:
        for idx in range(6):
            f_dice[idx] = n_dice[idx]
        for idx in range(6):
            if f_dice[idx] != target:
                for idx2 in range(6):
                    n_dice[idx2] = f_dice[idx2]
                n_dice[idx] = target
                break
        print(*n_dice)
        sys.stdout.flush()
        turn += 1
        d, v, x = MAP()
        score += v
        if points[x] == -1:
            points[x] = float(v)
        if x > n - target * 8:
            target = 1
        if x == n:
            x = 0
            break
        
    debug('first cycle finish in turn', turn)
    proc_point()
    init_data()
    debug('data initialize done')

    p_num_1 = 4
    dice3 = 1
    dice4 = 1
    while turn < m:
        max_point = -inf
        for num_1 in [p_num_1 - 1, p_num_1 + 1]:
            if 0 <= num_1 <= 4:
                point = data[x][num_1][dice3 - 1][dice4 - 1]
                if point > max_point:
                    max_point = point
                    n_num_1 = num_1
                    n_dice3 = dice3
                    n_dice4 = dice4
        for dice in range(1, 7):
            point = data[x][p_num_1][dice3 - 1][dice - 1]
            if point > max_point:
                max_point = point
                n_num_1 = p_num_1
                n_dice3 = dice3
                n_dice4 = dice
            point = data[x][p_num_1][dice - 1][dice4 - 1]
            if point > max_point:
                max_point = point
                n_num_1 = p_num_1
                n_dice3 = dice
                n_dice4 = dice4
        p_num_1 = n_num_1
        dice3 = n_dice3
        dice4 = n_dice4
        for idx in range(p_num_1):
            n_dice[idx] = 1
        for idx in range(p_num_1, 4):
            n_dice[idx] = 6
        n_dice[4] = dice3
        n_dice[5] = dice4
        print(*n_dice)
        sys.stdout.flush()
        turn += 1
        d, v, x = MAP()
        score += v
        if x == n:
            x = 0
    debug('time', time() - all_strt)

main()

Submission Info

Judge Result