import sys from collections import namedtuple sys.setrecursionlimit(1_000_000) SolveResult = namedtuple("SolveResult", ["bipartite", "answer", "crossings", "components"]) MASK64 = (1 << 64) - 1 def splitmix64(x): x = (x + 0x9E3779B97F4A7C15) & MASK64 x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK64 x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK64 return x ^ (x >> 31) class TreapNode: __slots__ = ("key", "priority", "left", "right") def __init__(self, key): self.key = key self.priority = splitmix64((key[0] << 32) ^ key[1]) self.left = None self.right = None def rotate_right(root): nxt = root.left root.left = nxt.right nxt.right = root return nxt def rotate_left(root): nxt = root.right root.right = nxt.left nxt.left = root return nxt def treap_insert(root, key): if root is None: return TreapNode(key) if key < root.key: root.left = treap_insert(root.left, key) if root.left.priority < root.priority: root = rotate_right(root) elif key > root.key: root.right = treap_insert(root.right, key) if root.right.priority < root.priority: root = rotate_left(root) return root def treap_collect_range(root, lo_key, hi_key, out): if root is None: return if root.key >= lo_key: treap_collect_range(root.left, lo_key, hi_key, out) if lo_key <= root.key < hi_key: out.append(root.key) if root.key < hi_key: treap_collect_range(root.right, lo_key, hi_key, out) class ParityDsu: def __init__(self, n): self.parent = list(range(n)) self.parity = [0] * n self.size = [1] * n self.counts = [[1, 0] for _ in range(n)] def find(self, x): if self.parent[x] == x: return x, 0 root, root_parity = self.find(self.parent[x]) self.parity[x] ^= root_parity self.parent[x] = root return self.parent[x], self.parity[x] def unite(self, a, b): ra, pa = self.find(a) rb, pb = self.find(b) if ra == rb: return (pa ^ pb) == 1 link = pa ^ pb ^ 1 if self.size[ra] < self.size[rb]: self.parent[ra] = rb self.parity[ra] = link self.counts[rb][0] += self.counts[ra][link] self.counts[rb][1] += self.counts[ra][link ^ 1] self.size[rb] += self.size[ra] else: self.parent[rb] = ra self.parity[rb] = link self.counts[ra][0] += self.counts[rb][link] self.counts[ra][1] += self.counts[rb][link ^ 1] self.size[ra] += self.size[rb] return True def best_sum(self): total = 0 for i in range(len(self.parent)): if self.parent[i] == i: total += max(self.counts[i][0], self.counts[i][1]) return total def component_count(self): return sum(1 for i in range(len(self.parent)) if self.parent[i] == i) def parse_csv_array(text): values = [] for token in text.split(","): if token.strip() == "": continue value = int(token) if value < 0: raise ValueError("Array value is out of range") values.append(value) return values def read_csv_array(path): with open(path) as fin: return parse_csv_array(fin.read()) def build_intervals(a): if len(a) % 2 != 0: raise ValueError("Array length is odd") n = len(a) // 2 first = [-1] * n occurrences = [0] * n intervals = [] for pos, value in enumerate(a): if value < 0 or value >= n: raise ValueError("Array values must be in [0,n)") occurrences[value] += 1 if occurrences[value] == 1: first[value] = pos elif occurrences[value] == 2: intervals.append((first[value], pos)) else: raise ValueError("A value occurs more than twice") for count in occurrences: if count != 2: raise ValueError("A value does not occur exactly twice") intervals.sort(key=lambda iv: iv[0]) return intervals def crosses(lhs, rhs): if lhs[0] < rhs[0]: return lhs[0] < rhs[0] and rhs[0] < lhs[1] and lhs[1] < rhs[1] return rhs[0] < lhs[0] and lhs[0] < rhs[1] and rhs[1] < lhs[1] def solve_array(a): intervals = build_intervals(a) n = len(intervals) dsu = ParityDsu(n) active_by_right = None # treap of (right, index) crossings = 0 for i in range(n): left, right = intervals[i] crossing_keys = [] treap_collect_range(active_by_right, (left + 1, -1), (right, -1), crossing_keys) for _, other in crossing_keys: if not dsu.unite(i, other): return SolveResult(False, -1, crossings + 1, 0) crossings += 1 active_by_right = treap_insert(active_by_right, (right, i)) return SolveResult(True, dsu.best_sum(), crossings, dsu.component_count()) def brute_force_array(a): intervals = build_intervals(a) n = len(intervals) edges = [] for i in range(n): for j in range(i + 1, n): if crosses(intervals[i], intervals[j]): edges.append((i, j)) best = -1 for mask in range(1 << n): ok = True for u, v in edges: if ((mask >> u) & 1) == ((mask >> v) & 1): ok = False break if ok: best = max(best, bin(mask).count("1")) return SolveResult(best >= 0, best, len(edges), 0) def validate_all_words(n, word, counts, pos): if pos == 2 * n: fast = solve_array(word) brute = brute_force_array(word) assert fast.bipartite == brute.bipartite if fast.bipartite: assert fast.answer == brute.answer assert fast.crossings == brute.crossings return for value in range(n): if counts[value] == 2: continue counts[value] += 1 word[pos] = value validate_all_words(n, word, counts, pos + 1) counts[value] -= 1 def run_checkpoints(): assert solve_array([0, 1, 2, 1, 0, 2]).answer == 2 assert solve_array([0, 0, 1, 1, 2, 2]).answer == 3 assert not solve_array([0, 1, 2, 0, 1, 2]).bipartite for n in range(1, 5): word = [0] * (2 * n) counts = [0] * n validate_all_words(n, word, counts, 0) def main(argv): file_path = "resources/documents/1002_input.txt" do_checkpoints = True for arg in argv[1:]: if arg == "--skip-checkpoints": do_checkpoints = False elif arg.startswith("--file="): file_path = arg[len("--file="):] else: sys.stderr.write("Unknown argument: " + arg + "\n") return 1 if do_checkpoints: run_checkpoints() values = read_csv_array(file_path) result = solve_array(values) if not result.bipartite: sys.stderr.write("The interval crossing graph is not bipartite\n") return 2 print(result.answer) return 0 if __name__ == "__main__": sys.exit(main(sys.argv))