結果

問題 No.241 出席番号(1)
ユーザー burita083burita083
提出日時 2021-06-17 01:58:40
言語 PyPy3
(7.3.13)
結果
WA  
実行時間 -
コード長 2,486 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 87,080 KB
実行使用メモリ 98,460 KB
最終ジャッジ日時 2023-08-30 08:19:48
合計ジャッジ時間 12,437 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 169 ms
79,120 KB
testcase_01 AC 171 ms
79,316 KB
testcase_02 AC 171 ms
79,264 KB
testcase_03 AC 171 ms
79,232 KB
testcase_04 AC 169 ms
79,188 KB
testcase_05 AC 166 ms
79,152 KB
testcase_06 AC 165 ms
79,148 KB
testcase_07 AC 167 ms
79,200 KB
testcase_08 AC 165 ms
78,964 KB
testcase_09 AC 170 ms
79,292 KB
testcase_10 AC 169 ms
79,148 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 169 ms
79,504 KB
testcase_14 AC 179 ms
80,704 KB
testcase_15 AC 176 ms
80,836 KB
testcase_16 AC 117 ms
78,084 KB
testcase_17 AC 168 ms
79,068 KB
testcase_18 AC 169 ms
79,044 KB
testcase_19 AC 172 ms
79,160 KB
testcase_20 AC 170 ms
79,180 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 174 ms
80,932 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 176 ms
80,676 KB
testcase_27 WA -
testcase_28 AC 182 ms
80,668 KB
testcase_29 AC 177 ms
80,948 KB
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

# 最大流問題
from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  # to, cap, rev
        # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]]
        self.level = [0] * N

    def add_edge(self, u, v, cap):
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, 0, len(self.V[u])-1])

    def add_edge_undirected(self, u, v, cap):  # 未検証
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, cap, len(self.V[u])-1])

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  # capが1以上で未探索の辺
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  # 到達可能

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  # 増加路
                    e[CAP] -= d  # cap を減らす
                    self.V[e[TO]][e[REV]][CAP] += d  # 反対方向の cap を増やす
                    return d
        return 0

    def solve(self, s, g):
        self.g = g
        flow = 0
        while self.bfs(s):  # 到達可能な間
            self.ite = [0] * self.N
            f = self.dfs(s, INF)
            while f > 0:
                flow += f
                f = self.dfs(s, INF)
        return flow


N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
dp = [set() for i in range(N)]
for i, x in enumerate(A):
  for j in range(N):
    if j != x:
      dp[i].add(j)

ans = -float('inf')
import random
l = []
for i in range(100000):
  st = set()
  temp = 0
  for d in dp:
    d -= st
    while True:
      if len(d) == 0:
        break
      item = random.sample(d, 1)
      if not item[0] in st:
        st.add(item[0])
        l.append(item[0])
        temp += 1
        break
  if temp == N:
    break
if len(l) < N:
  print(-1)
  exit()
for d in l:
  print(d)
0