import heapq import sys import math import time debug = True t0 = time.time() def log(*msg): if debug: print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr, flush=True) def time_to(total, step): """ number of steps to reach total """ return total // step + (1 if total % step > 0 else 0) class BaseClass: def __repr__(self): return f"<{self.__class__.__name__}: {self.__dict__}>" class Queue(BaseClass): def __init__(self): self.items = [] def __bool__(self): return bool(self.items) def __repr__(self): return str(self.items) def values(self): return (v for _, v in self.items) def put(self, priority, item): while priority in [p for p, _ in self.items]: priority += 1 heapq.heappush(self.items, (priority, item)) def get(self): return heapq.heappop(self.items)[1] def get_items(self): return heapq.heappop(self.items) class Player(BaseClass): def __init__(self, id_): self.id = id_ ME = Player(int(input())) # Input gives the player id: 0 plays first OPPONENT = Player(1 - ME.id) PLAYERS_INDEX = {p.id: p for p in [ME, OPPONENT]} PLAYERS_ORDER = sorted([ME, OPPONENT], key=lambda p: p.id) class Unit(BaseClass): TYPE_CULTIST = 0 TYPE_CULT_LEADER = 1 OWNER_0 = 0 OWNER_1 = 1 NO_OWNER = 2 SHOOTING_RANGE = 6 SHOOTING_MAX_DAMAGE = 7 def __init__(self, id_): self.id = id_ self.hp = 10 self.x = None self.y = None self.owner = None @property def pos(self): return self.x, self.y @property def owned(self): return self.owner == ME.id @property def opponent(self): return self.owner == OPPONENT.id @property def neutral(self): return self.owner == self.NO_OWNER class CultLeader(Unit): pass class Action(BaseClass): pass class ActionWait(Action): def __repr__(self): return f"" def exec(self): print("WAIT") class ActionMove(Action): def __init__(self, unit, pos): self.unit = unit self.pos = pos def __repr__(self): return f"" def exec(self): print(f"{self.unit.id} MOVE {self.pos[0]} {self.pos[1]}") class ActionShoot(Action): def __init__(self, unit, target): self.unit = unit self.target = target def __repr__(self): return f"" def exec(self): print(f"{self.unit.id} SHOOT {self.target.id}") class ActionConvert(Action): def __init__(self, unit, target): self.unit = unit self.target = target def __repr__(self): return f"" def exec(self): print(f"{self.unit.id} CONVERT {self.target.id}") class Grid(BaseClass): def __init__(self, width, height): self.width = width self.height = height self.obstacles = [] self.index = {} self.units = {} self.round = 0 def prepare_round(self): self.units = {} def update_unit(self, id_, type_, hp, x, y, owner): self.units[id_] = Unit(id_) if type_ != Unit.TYPE_CULT_LEADER else CultLeader(id_) unit = self.units[id_] unit.hp = hp unit.x = x unit.y = y unit.owner = owner def update_index(self): self.index = {} for unit in self.units.values(): self.index[(unit.x, unit.y)] = unit def own_cult_leader(self): return next(u for u in self.units.values() if type(u) is CultLeader and u.owned) def allied_cultists(self): return [u for u in self.units.values() if type(u) is not CultLeader and u.owned] def opponent_units(self): return [u for u in self.units.values() if u.opponent] def opponent_cult_leader(self): return [u for u in self.units.values() if type(u) is CultLeader and not u.owned] def opponent_cultists(self): return [u for u in self.units.values() if type(u) is not CultLeader and u.opponent] def neutrals(self): return [u for u in self.units.values() if u.neutral] def list_actions(self): actions = Queue() k_convert_neutrals = 10 k_convert_danger = 30 k_shoot_opponent_cultist = 20 k_shoot_opponent_cult_leader = 10 k_limit = 200 cult_leader = self.own_cult_leader() for n in self.neutrals(): action = ActionConvert(cult_leader, n) distance = self.manhattan(cult_leader.pos, n.pos) danger = 0 for u in self.opponent_cultists(): fire_dist = self.fire_dist(cult_leader.pos, u.pos) if fire_dist < u.SHOOTING_RANGE: danger += (u.SHOOTING_MAX_DAMAGE - fire_dist) priority = k_convert_neutrals * distance + k_convert_danger * danger if priority > k_limit: continue actions.put(priority, action) for a in self.allied_cultists(): for u in self.opponent_cultists(): fire_dist = self.fire_dist(a.pos, u.pos) if fire_dist < u.SHOOTING_RANGE: action = ActionShoot(a, u) priority = (k_shoot_opponent_cult_leader if type( u) is CultLeader else k_shoot_opponent_cultist) * fire_dist if priority > k_limit: continue actions.put(priority, action) return actions def in_grid(self, pos): return 0 <= pos[0] < self.width and 0 <= pos[1] < self.height def can_see_trough(self, pos): return self.in_grid(pos) and pos not in self.obstacles + list(self.index.values()) def can_move_on(self, pos): return self.in_grid(pos) and pos not in self.obstacles + list(self.index.values()) @staticmethod def manhattan(from_, to_): xa, ya = from_ xb, yb = to_ return abs(xa - xb) + abs(ya - yb) @classmethod def line(cls, from_, to_): """ Implementation of bresenham's algorithm """ xa, ya = from_ xb, yb = to_ if (xa, ya) == (xb, yb): return [(xa, ya)] # diagonal symmetry vertically_oriented = (abs(yb - ya) > abs(xb - xa)) if vertically_oriented: ya, xa, yb, xb = xa, ya, xb, yb # horizontal symmetry reversed_sym = (xa > xb) if reversed_sym: xb, yb, xa, ya = xa, ya, xb, yb # angle dx, dy = xb - xa, yb - ya alpha = (abs(dy) / dx) offset = 0.0 step = 1 if dy > 0 else -1 result = [] y_ = ya for x_ in range(xa, xb + 1): result.append((y_, x_) if vertically_oriented else (x_, y_)) offset += alpha if offset > 0.5: y_ += step offset -= 1.0 if reversed_sym: result.reverse() return result def fire_line(self, from_, to_): line = self.line(from_, to_) return line if all(self.can_see_trough(c) for c in line) else [] def fire_dist(self, from_, to_): return len(self.fire_line(from_, to_)) # Create grid GRID = Grid(*[int(i) for i in input().split()]) GRID.obstacles = [(i, j) for i in range(GRID.height) for j, val in enumerate(input()) if val == 'x'] while 1: # TODO: prendre en compte le terrain dans la ligne de visée et les déplacements GRID.prepare_round() for _ in range(int(input())): GRID.update_unit(*[int(j) for j in input().split()]) GRID.update_index() actions = GRID.list_actions() for action in actions.items: log(f"* {action}") try: action = actions.get() except IndexError: log("no action...") action = ActionWait() log(f"exec : {action}") action.exec() GRID.round += 1