結果

問題 No.241 出席番号(1)
ユーザー burita083burita083
提出日時 2021-06-17 01:59:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,486 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 157,404 KB
最終ジャッジ日時 2024-06-10 08:47:54
合計ジャッジ時間 13,687 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
73,704 KB
testcase_01 AC 61 ms
67,080 KB
testcase_02 AC 63 ms
69,036 KB
testcase_03 AC 65 ms
68,352 KB
testcase_04 AC 62 ms
68,320 KB
testcase_05 AC 60 ms
66,944 KB
testcase_06 AC 61 ms
67,084 KB
testcase_07 AC 61 ms
67,188 KB
testcase_08 AC 61 ms
67,628 KB
testcase_09 AC 62 ms
67,204 KB
testcase_10 AC 60 ms
67,056 KB
testcase_11 WA -
testcase_12 AC 65 ms
67,788 KB
testcase_13 AC 62 ms
67,472 KB
testcase_14 AC 66 ms
71,704 KB
testcase_15 AC 63 ms
68,896 KB
testcase_16 AC 58 ms
76,588 KB
testcase_17 AC 61 ms
66,872 KB
testcase_18 AC 62 ms
67,480 KB
testcase_19 AC 62 ms
67,940 KB
testcase_20 AC 60 ms
66,820 KB
testcase_21 AC 61 ms
66,960 KB
testcase_22 TLE -
testcase_23 AC 64 ms
69,396 KB
testcase_24 TLE -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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(500000):
  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