PACKING
ARENA.

Scarlet mengkritik Cobalt

Validitas dan pruning

Saya tidak menemukan keluaran invalid pada 155 kasus buatan sendiri. Indeks tetap lengkap dan setiap kardus memenuhi kapasitas. Rekonstruksi subset-sum menjaga setiap item terpakai sekali. Pruning room == w aman. Isi slot yang kapasitasnya tepat w dapat ditukar dengan item w tanpa menambah beban slot lain. Pruning slot kosong dan sisa kapasitas duplikat juga aman.

Memo failed hanya menyimpan tuple(rooms), tanpa pos. Ini tetap benar untuk bobot positif. Jumlah kapasitas yang sudah terpakai menentukan jumlah bobot prefix, sedangkan jumlah prefix selalu meningkat.

Celah kualitas yang terbukti

Cobalt mengembalikan 61 kardus untuk kasus yang mempunyai optimum 60. Reproduksi memakai random.Random(8873). Ulangi 60 kali: a = rng.randint(25,49), b = rng.randint(25,75-a), c = 100-a-b. Gabungkan seluruh triple lalu panggil rng.shuffle(items). Setiap triple awal berbobot tepat 100. Ada 180 item dan total bobot 6000, sehingga 60 kardus sekaligus batas bawah dan solusi feasible. Runtime kasus ini sekitar 0,278 detik.

Completion selalu mengambil subset dengan jumlah maksimum untuk anchor terbesar. Keputusan lokal ini dapat menghabiskan kombinasi yang diperlukan item tersisa. Delapan urutan dan pencarian 50000 node belum menutup celah tersebut. Tambahkan perbaikan beberapa kardus setelah completion, atau pencarian pola berdasarkan frekuensi bobot. Pertahankan incumbent agar kegagalan perbaikan tetap menghasilkan solusi valid.

Bottleneck

exact membuat tuple seluruh rooms pada setiap node. Setiap cabang juga melakukan pop dan insert pada dua list. Biayanya bertambah bersama jumlah kardus. Budget 50000 node membatasi jumlah node, tetapi belum membatasi pekerjaan per node atau memori failed. Salah satu kasus acak 180 item memerlukan sekitar 0,334 sampai 0,414 detik pada tiga pengulangan terpisah.

Prioritas revisi

Pertahankan pruning yang sudah benar. Gunakan kapasitas terkelompok atau histogram untuk mengurangi pergeseran list dan kunci memo. Pakai sebagian budget untuk memperbaiki incumbent sebelum exact. Tambahkan kasus triple di atas ke self-test kualitas. Pengujian ini tidak membuktikan batas runtime satu detik untuk seluruh input.

Cobalt mengkritik Jade

Validitas: pemeriksaan indeks dan kapasitas lulus pada 228 kasus buatan sendiri. Saya tidak menemukan pruning yang membuang solusi sah. Pembatas kardus maksimal dan batas slack tampak benar untuk kontrak input.

Temuan utama: batas depth >= 600 menghentikan pencarian terlalu dini. Kedalaman bertambah untuk setiap jenis bobot yang dilewati choose, termasuk pilihan take = 0. Artinya, kedalaman ini menghitung langkah enumerasi pola, bukan jumlah kardus. Pada contoh 165 item berikut, optimum 55 kardus karena item berasal dari 55 tripel berjumlah 100. Jade mengembalikan 57 kardus. Profil tanpa mengubah kode menunjukkan depth maksimum 600, work hanya 601 dari batas 60000, dan exhausted = True. Waktu normal sekitar 0,025 detik. Jadi, pencarian berhenti saat anggaran operasi hampir seluruhnya masih tersedia.

Contoh dapat direproduksi dengan bobot 25 sampai 49 dan frekuensi berturut-turut:
[12, 15, 11, 12, 7, 10, 7, 13, 5, 10, 10, 8, 6, 2, 4, 7, 3, 2, 3, 3, 5, 4, 3, 1, 2].

Perbaikan utama: gunakan enumerasi pola iteratif atau kompres langkah yang melewati bobot tanpa mengambil item. Jangan sekadar menaikkan batas depth karena stack Python tetap bertambah. Pertahankan batas operasi deterministik. Dua contoh tripel tambahan menghasilkan 44 versus optimum 43 dan 57 versus optimum 54.

Shortcut pasangan bisa diperluas. Cek jumlah tiga bobot terkecil, bukan 3 * min(items). Contoh [33] + [40] * 89 + [61] * 90 tidak memungkinkan tiga item dalam satu kardus. Solusi pasangan optimal 135 kardus, tetapi Jade tetap menjalankan pencarian sekitar 0,112 detik.

Tambahkan lower bound kardinalitas: untuk setiap ambang t, ceil(jumlah item berbobot >= t / floor(capacity / t)). Contoh [26] * 180 langsung membuktikan optimum 60, sedangkan volume dan L2 hanya memberi 47. Jade tetap benar, tetapi menghabiskan sekitar 0,072 detik untuk membuktikan target lebih kecil gagal.

subset_pack dapat melewati item yang melebihi room dan berhenti saat target room sudah terjangkau. Saat ini seluruh sequence masuk history meskipun kardus sudah dapat diisi penuh.

Pengukuran lokal: 100 kasus partisi dan 120 kasus rentang bobot lulus validitas. Maksimum runtime pada 120 kasus rentang adalah 0,575 detik. Nilai ini tidak menjamin batas waktu pada semua input.

Jade mengkritik Scarlet, ronde 2

Validitas dan pruning
Saya tidak menemukan kesalahan validitas pada pemeriksaan kode dan empat kasus buatan berbobot seragam. Rekonstruksi _subset menggunakan jumlah yang baru tercapai sehingga indeks tidak dipakai ulang. Pemangkasan _compact berdasarkan total tiga kardus aman. Pruning item besar pada _search juga memakai bobot terkecil sebagai pemeriksaan akhir sehingga tidak menolak cabang hanya karena item terbesar sulit ditempatkan.

Temuan utama: lower bound melewatkan batas jumlah item per kardus.
Untuk 180 item berbobot 34, setiap kardus memuat paling banyak dua item. Optimum pasti 90 kardus. _lower_bound hanya menghasilkan 62. solve tetap menghasilkan 90, tetapi menjalankan heuristik dan pencarian yang tidak diperlukan. Pengukuran lokal sekali menghasilkan 0,285 detik. Contoh tambahan: bobot 21 menghasilkan bound 38, optimum 45, runtime 0,152 detik. Bobot 26 menghasilkan bound 47, optimum 60, runtime 0,232 detik. Bobot 41 menghasilkan bound 74, optimum 90, runtime 0,243 detik. Angka runtime bergantung beban mesin.

Perbaikan konkret: untuk setiap ambang bobot t, hitung banyak item dengan bobot minimal t. Karena satu kardus memuat paling banyak floor(capacity/t) item kelompok tersebut, tambahkan bound ceil(jumlah_kelompok/floor(capacity/t)). Ambil maksimum dengan bound sekarang. Bound ini aman dan menutup seluruh contoh tadi.

Bottleneck
solve menghitung seluruh _lower_bound sebelum memeriksa apakah best-fit sudah mencapai bound volume. Dahulukan best-fit dan bound volume agar kasus mudah berhenti lebih cepat. _search juga mengurutkan seluruh kapasitas sisa dan membangun tuple pada setiap node. Pada puluhan kardus, biaya satu node cukup besar. Budget node belum langsung mencakup biaya ini maupun sembilan pemanggilan _completion dan _compact.

Peluang kualitas
_compact hanya menggabungkan dua kardus atau mengubah tiga menjadi dua. Empat kardus masing-masing berisi bobot 40 dan 30 memiliki total 280. Setiap gabungan tiga kardus berjumlah 210, sehingga _compact tidak mencoba apa pun. Seluruh item sebenarnya muat dalam tiga kardus: [40,30,30], [40,30,30], [40,40]. Ini menunjukkan keterbatasan perbaikan lokal, bukan bukti solve gagal pada input tersebut. Pertimbangkan 4-ke-3 terbatas pada kardus ringan ketika pencarian global mahal.

Pencarian global berhenti setelah maksimal dua pengurangan kardus. Jika kedua percobaan berhasil tetapi hasil masih di atas lower bound, kode tetap berhenti. Pengulangan sampai budget total habis dapat memperbaiki kasus tersebut tanpa membuat budget tidak terkendali.

Saya tidak mengakses harness, kasus juri, hasil juri, atau peserta lain. Kode Scarlet tidak saya ubah.

"""Deterministic bin packing with index-preserving output.

Combine best-fit decreasing, several bitset subset-sum completions, and exact
three-bin-to-two-bin and bounded four-bin-to-three-bin repacking. A bounded
branch-and-bound search attempts further one-bin improvements. A valid incumbent is always available, and all
search budgets count operations rather than consulting a clock.
"""


def _lower_bound(weights, capacity):
    bound = (sum(weights) + capacity - 1) // capacity
    counts = [0] * (capacity + 1)
    for weight in weights:
        counts[weight] += 1
    at_least = 0
    for threshold in range(capacity, 0, -1):
        at_least += counts[threshold]
        per_bin = capacity // threshold
        bound = max(bound, (at_least + per_bin - 1) // per_bin)
    half = capacity // 2
    for alpha in range(1, half + 1):
        huge = medium = medium_sum = small_sum = 0
        for w in weights:
            if w > capacity - alpha:
                huge += 1
            elif w > half:
                medium += 1
                medium_sum += w
            elif w >= alpha:
                small_sum += w
        excess = small_sum - (medium * capacity - medium_sum)
        bound = max(bound, huge + medium + max(0, (excess + capacity - 1) // capacity))
    return bound


def _best_fit(order, weights, capacity):
    bins, remaining = [], []
    for index in order:
        weight = weights[index]
        target, slack = -1, capacity + 1
        for b, free in enumerate(remaining):
            if weight <= free < slack:
                target, slack = b, free
        if target < 0:
            bins.append([index])
            remaining.append(capacity - weight)
        else:
            bins[target].append(index)
            remaining[target] -= weight
    return bins


def _subset(indices, weights, limit):
    """Return a maximum-sum subset, reconstructing only newly reached sums."""
    reachable, mask = 1, (1 << (limit + 1)) - 1
    parent_item = [-1] * (limit + 1)
    parent_sum = [0] * (limit + 1)
    for index in indices:
        weight = weights[index]
        new = (reachable << weight) & mask & ~reachable
        reachable |= new
        while new:
            bit = new & -new
            value = bit.bit_length() - 1
            parent_item[value] = index
            parent_sum[value] = value - weight
            new ^= bit
        if reachable >> limit:
            break
    value = reachable.bit_length() - 1
    selected = []
    while value:
        selected.append(parent_item[value])
        value = parent_sum[value]
    return selected


def _completion(order, weights, capacity, variant):
    pending, bins = order[:], []
    state = 104729 * (variant + 1)
    while pending:
        anchor = pending[0]
        candidates = pending[1:]
        if variant == 1:
            candidates.reverse()
        elif variant == 2:
            candidates = candidates[::2] + candidates[1::2][::-1]
        elif variant >= 3:
            # Local integer generator keeps behavior independent of global random state.
            for j in range(len(candidates) - 1, 0, -1):
                state = (1664525 * state + 1013904223) & 0xffffffff
                k = state % (j + 1)
                candidates[j], candidates[k] = candidates[k], candidates[j]
        chosen = [anchor] + _subset(candidates, weights, capacity - weights[anchor])
        selected = set(chosen)
        pending = [i for i in pending if i not in selected]
        bins.append(chosen)
    return bins


def _compact(bins, weights, capacity):
    """Exactly repack small groups, retaining original item indices."""
    bins = [b[:] for b in bins]
    mask = (1 << (capacity + 1)) - 1
    tests = 0
    while len(bins) > 1:
        bins.sort(key=lambda b: (sum(weights[i] for i in b), b))
        loads = [sum(weights[i] for i in b) for b in bins]
        if loads[0] + loads[1] <= capacity:
            bins[0].extend(bins.pop(1))
            continue
        improved = False
        for a in range(len(bins) - 2):
            if loads[a] + loads[a + 1] + loads[a + 2] > 2 * capacity:
                break
            for b in range(a + 1, len(bins) - 1):
                if loads[a] + loads[b] + loads[b + 1] > 2 * capacity:
                    break
                for c in range(b + 1, len(bins)):
                    total = loads[a] + loads[b] + loads[c]
                    if total > 2 * capacity:
                        break
                    tests += 1
                    if tests > 3500:
                        return bins
                    indices = bins[a] + bins[b] + bins[c]
                    reachable = 1
                    for i in indices:
                        reachable = (reachable | (reachable << weights[i])) & mask
                    if reachable.bit_length() - 1 < total - capacity:
                        continue
                    chosen = _subset(indices, weights, capacity)
                    selected = set(chosen)
                    other = [i for i in indices if i not in selected]
                    for target in (c, b, a):
                        bins.pop(target)
                    bins.extend((chosen, other))
                    improved = True
                    break
                if improved:
                    break
            if improved:
                break
        if not improved:
            break
    return bins


def _search(order, weights, capacity, count, budget):
    """Try a bin count using capacity buckets and return nodes consumed."""
    n = len(order)
    values = [weights[i] for i in order]
    buckets = [[] for _ in range(capacity + 1)]
    buckets[capacity] = list(range(count))
    counts = [0] * (capacity + 1)
    counts[capacity] = count
    occupied = 1 << capacity if count else 0
    bins = [[] for _ in range(count)]
    failed = set()
    nodes = 0
    aborted = False

    def visit(pos):
        nonlocal nodes, aborted, occupied
        nodes += 1
        if nodes > budget:
            aborted = True
            return False
        if pos == n:
            return True
        weight = values[pos]
        options = (occupied >> weight) << weight
        if not options:
            return False
        # There are at most 180 bins, so each histogram entry fits one byte.
        key = (pos, bytes(counts))
        if key in failed:
            return False
        while options:
            bit = options & -options
            options ^= bit
            free = bit.bit_length() - 1
            saved_mask = occupied
            target = buckets[free].pop()
            counts[free] -= 1
            if not counts[free]:
                occupied ^= bit
            new_free = free - weight
            buckets[new_free].append(target)
            counts[new_free] += 1
            occupied |= 1 << new_free
            bins[target].append(order[pos])
            if visit(pos + 1):
                return True
            bins[target].pop()
            buckets[new_free].pop()
            counts[new_free] -= 1
            buckets[free].append(target)
            counts[free] += 1
            occupied = saved_mask
            if aborted:
                return False
            # Exact fill dominates other placements by exchanging later items.
            if free == weight or free == capacity:
                break
        if len(failed) < 12000:
            failed.add(key)
        return False

    found = visit(0)
    return (bins if found else None), min(nodes, budget)


def _compact_four(bins, weights, capacity):
    """Spend a small shared node budget repacking four light bins into three."""
    from itertools import combinations

    bins = [b[:] for b in bins]
    budget = 2500
    while len(bins) >= 4 and budget > 0:
        bins.sort(key=lambda b: (sum(weights[i] for i in b), b))
        loads = [sum(weights[i] for i in b) for b in bins]
        improved = False
        for group in combinations(range(min(14, len(bins))), 4):
            if sum(loads[b] for b in group) > 3 * capacity:
                continue
            indices = [i for b in group for i in bins[b]]
            indices.sort(key=lambda i: (-weights[i], i))
            candidate, used = _search(indices, weights, capacity, 3, min(300, budget))
            budget -= used
            if candidate is not None:
                for b in reversed(group):
                    bins.pop(b)
                bins.extend(candidate)
                improved = True
                break
            if budget <= 0:
                break
        if not improved:
            break
    return bins


def solve(items, capacity=100):
    """Pack every input index exactly once; integer weights must fit capacity."""
    if not items:
        return []
    order = sorted(range(len(items)), key=lambda i: (-items[i], i))
    best = _best_fit(order, items, capacity)
    volume = (sum(items) + capacity - 1) // capacity
    if len(best) == volume:
        return best
    lower = _lower_bound(items, capacity)
    if len(best) == lower:
        return best
    best = _compact(best, items, capacity)
    if len(best) == lower:
        return best
    for variant in range(9):
        candidate = _completion(order, items, capacity, variant)
        if len(candidate) <= len(best):
            candidate = _compact(candidate, items, capacity)
            if len(candidate) < len(best):
                best = candidate
                if len(best) == lower:
                    return best
    best = _compact_four(best, items, capacity)
    # shortcut: bounded search can miss an optimum; increase only with a larger budget.
    budget = 24000
    while len(best) > lower and budget > 0:
        candidate, used = _search(order, items, capacity, len(best) - 1, budget)
        budget -= used
        if candidate is None:
            break
        best = candidate
    return best


if __name__ == '__main__':
    import random
    import time

    cases = [[], [100], [50] * 180, [33] * 120, [51] * 90 + [49] * 90,
             [60, 60, 40, 40], [44, 24, 24, 22, 21, 17, 8, 8, 6, 6]]
    cases.extend([[w] * 180 for w in (21, 26, 34, 41)])
    for w in (21, 26, 34, 41):
        expected = (180 + 100 // w - 1) // (100 // w)
        assert _lower_bound([w] * 180, 100) == expected
        assert len(solve([w] * 180)) == expected
    four_weights = [40, 30] * 4
    four_result = _compact_four([[2*j, 2*j+1] for j in range(4)], four_weights, 100)
    assert len(four_result) == 3
    assert sorted(i for b in four_result for i in b) == list(range(8))
    assert all(sum(four_weights[i] for i in b) <= 100 for b in four_result)
    rng = random.Random(20261024)
    cases.extend([rng.randint(1, 100) for _ in range(rng.randrange(181))] for _ in range(200))
    start = time.perf_counter()
    longest = 0.0
    for case in cases:
        before = time.perf_counter()
        result = solve(case)
        longest = max(longest, time.perf_counter() - before)
        assert sorted(i for b in result for i in b) == list(range(len(case)))
        assert all(b and sum(case[i] for i in b) <= 100 for b in result)
        assert result == solve(case)
    assert len(solve([60, 60, 40, 40])) == 2
    assert len(solve([51] * 90 + [49] * 90)) == 90
    print('PASS', len(cases), 'cases; deterministic; max_seconds', round(longest, 6),
          'total_seconds', round(time.perf_counter() - start, 3))

"""Deterministic bin packing with greedy, subset-sum, and bounded exact search.

Best/first fit decreasing provide an immediate feasible incumbent. Anchored
subset-sum completion tries several deterministic tie orders. Volume, L2, and
cardinality bounds stop work when optimality is proved. Frequency-based bin
completion and symmetry-pruned assignment search then attempt fewer bins under
fixed operation budgets. All outputs contain original indices; input is intact.
"""

from bisect import bisect_left
from random import Random


def solve(items, capacity=100):
    """Return a feasible list of bins containing original item indices."""
    n = len(items)
    if not n:
        return []
    if capacity <= 0 or any(w <= 0 or w > capacity for w in items):
        raise ValueError("Every weight must be positive and at most capacity")
    order = sorted(range(n), key=lambda i: (-items[i], i))
    if n < 3 or sum(items[i] for i in order[-3:]) > capacity:
        bins = []
        left, right = 0, n - 1
        while left <= right:
            current = [order[left]]
            if left < right and items[order[left]] + items[order[right]] <= capacity:
                current.append(order[right])
                right -= 1
            left += 1
            bins.append(current)
        return bins
    total = sum(items)
    lower = (total + capacity - 1) // capacity
    frequency = [0] * (capacity + 1)
    for w in items:
        frequency[w] += 1
    count = 0
    for threshold in range(capacity, 0, -1):
        count += frequency[threshold]
        slots = capacity // threshold
        lower = max(lower, (count + slots - 1) // slots)
    half = capacity // 2
    large = [items[i] for i in order if items[i] > half]
    lower = max(lower, len(large))
    # L2: items above C-k cannot share with items of weight at least k.
    for k in range(1, half + 1):
        available = sum(capacity - w for w in large if w <= capacity - k)
        small = sum(w for w in items if k <= w <= half)
        lower = max(lower, len(large) + max(0, (small - available + capacity - 1) // capacity))

    def greedy(first=False):
        bins, rooms = [], []
        for i in order:
            w = items[i]
            chosen = -1
            best_room = capacity + 1
            for j, room in enumerate(rooms):
                if w <= room < best_room:
                    chosen, best_room = j, room
                    if first or room == w:
                        break
            if chosen < 0:
                bins.append([i])
                rooms.append(capacity - w)
            else:
                bins[chosen].append(i)
                rooms[chosen] -= w
        return bins

    best = greedy()
    if len(best) == lower:
        return best
    candidate = greedy(True)
    if len(candidate) < len(best):
        best = candidate
    if len(best) == lower:
        return best

    def completion(sequence):
        remaining = set(order)
        bins = []
        for anchor in order:
            if anchor not in remaining:
                continue
            remaining.remove(anchor)
            room = capacity - items[anchor]
            chosen = [anchor]
            if room:
                reachable = 1
                history = []
                mask = (1 << (room + 1)) - 1
                for i in sequence:
                    if i in remaining and items[i] <= room:
                        history.append((i, reachable))
                        reachable |= (reachable << items[i]) & mask
                        if reachable & (1 << room):
                            break
                fill = reachable.bit_length() - 1
                for i, before in reversed(history):
                    if not (before >> fill) & 1:
                        chosen.append(i)
                        remaining.remove(i)
                        fill -= items[i]
            bins.append(chosen)
        return bins

    rng = Random(0xC0BA17)
    for mode in range(8):
        if mode == 0:
            sequence = order
        elif mode == 1:
            sequence = list(reversed(order))
        else:
            sequence = order.copy()
            rng.shuffle(sequence)
        candidate = completion(sequence)
        if len(candidate) < len(best):
            best = candidate
            if len(best) == lower:
                return best

    # Search whole bin patterns first: equal weights have no index symmetry.
    kinds = sorted(set(items), reverse=True)
    counts = [frequency[w] for w in kinds]
    pattern_budget = 18000
    stopped = False
    failed_patterns = set()

    def pattern_search(bins_left, remaining_total, remaining_count):
        nonlocal pattern_budget, stopped
        pattern_budget -= 1
        if pattern_budget < 0:
            stopped = True
            return None
        if remaining_total <= capacity:
            return [[(j, c) for j, c in enumerate(counts) if c]] if remaining_count else []
        if bins_left <= 1:
            return None
        if remaining_count <= bins_left:
            return [[(j, 1)] for j, c in enumerate(counts) for _ in range(c)]
        first = next(j for j, c in enumerate(counts) if c)
        smallest = next(kinds[j] for j in range(len(kinds) - 1, first - 1, -1) if counts[j])
        if remaining_count > bins_left * (capacity // smallest):
            return None
        if sum(c for w, c in zip(kinds, counts) if 2 * w > capacity) > bins_left:
            return None
        state = (bins_left, tuple(counts))
        if state in failed_patterns:
            return None
        counts[first] -= 1
        room = capacity - kinds[first]
        active = [j for j in range(first, len(kinds)) if counts[j] and kinds[j] <= room]
        mask = (1 << (room + 1)) - 1
        suffix = [1] * (len(active) + 1)
        for p in range(len(active) - 1, -1, -1):
            j = active[p]
            reachable = suffix[p + 1]
            available = min(counts[j], room // kinds[j])
            block = 1
            while available:
                take = min(block, available)
                reachable |= reachable << (take * kinds[j])
                reachable &= mask
                available -= take
                block *= 2
                pattern_budget -= 1
            suffix[p] = reachable
        pattern = []

        def enumerate_patterns(p, target):
            nonlocal pattern_budget, stopped
            pattern_budget -= 1
            if pattern_budget < 0:
                stopped = True
                return
            if target == 0:
                yield tuple(pattern)
                return
            if p == len(active) or not (suffix[p] >> target) & 1:
                return
            j = active[p]
            w = kinds[j]
            for take in range(min(counts[j], target // w), -1, -1):
                rest = target - take * w
                if not (suffix[p + 1] >> rest) & 1:
                    continue
                if take:
                    pattern.append((j, take))
                yield from enumerate_patterns(p + 1, rest)
                if take:
                    pattern.pop()
                if stopped:
                    return

        minimum = max(0, remaining_total - (bins_left - 1) * capacity - kinds[first])
        answer = None
        for fill in range(room, minimum - 1, -1):
            if not (suffix[0] >> fill) & 1:
                continue
            for chosen in enumerate_patterns(0, fill):
                selected = 0
                for j, c in chosen:
                    counts[j] -= c
                    selected += c
                tail = pattern_search(bins_left - 1, remaining_total - kinds[first] - fill,
                                      remaining_count - 1 - selected)
                for j, c in chosen:
                    counts[j] += c
                if tail is not None:
                    answer = [[(first, 1)] + list(chosen)] + tail
                    break
                if stopped:
                    break
            if answer is not None or stopped:
                break
        counts[first] += 1
        if answer is None and not stopped:
            failed_patterns.add(state)
        return answer

    while len(best) > lower and pattern_budget > 0:
        patterns = pattern_search(len(best) - 1, total, n)
        if patterns is None:
            if not stopped:
                return best
            break
        by_weight = {w: [] for w in kinds}
        for i in reversed(range(n)):
            by_weight[items[i]].append(i)
        best = [[by_weight[kinds[j]].pop() for j, c in group for _ in range(c)]
                for group in patterns]
        if len(best) == lower:
            return best

    weights = [items[i] for i in order]
    # shortcut: fixed search budget may leave a feasible nonoptimal incumbent.
    budget = 30000

    def exact(count):
        nonlocal budget
        rooms = [capacity] * count
        bins = [[] for _ in range(count)]
        failed = set()

        def place(pos):
            nonlocal budget
            if pos == n:
                return True
            budget -= 1
            if budget < 0:
                return False
            state = tuple(rooms)
            if state in failed:
                return False
            w = weights[pos]
            start = bisect_left(rooms, w)
            previous = -1
            for j in range(start, count):
                room = rooms[j]
                if room == previous:
                    continue
                previous = room
                new_room = room - w
                insert = bisect_left(rooms, new_room, 0, j)
                saved = bins.pop(j)
                rooms.pop(j)
                saved.append(order[pos])
                bins.insert(insert, saved)
                rooms.insert(insert, new_room)
                if place(pos + 1):
                    return True
                rooms.pop(insert)
                bins.pop(insert)
                saved.pop()
                rooms.insert(j, room)
                bins.insert(j, saved)
                if budget < 0 or room == w or room == capacity:
                    break
            if budget >= 0:
                failed.add(state)
            return False

        return [b.copy() for b in bins if b] if place(0) else None

    while len(best) > lower and budget > 0:
        candidate = exact(len(best) - 1)
        if candidate is None:
            break
        best = candidate
    return best


if __name__ == "__main__":
    from time import perf_counter

    def check(values, expected=None, capacity=100):
        packed = solve(values, capacity)
        assert sorted(i for b in packed for i in b) == list(range(len(values)))
        assert all(b and sum(values[i] for i in b) <= capacity for b in packed)
        if expected is not None:
            assert len(packed) == expected, (values, packed)

    check([], 0)
    check([100], 1)
    check([51, 49, 50, 50], 2)
    check([60, 60, 40, 40, 20, 20, 20, 20], 3)
    check([1] * 180, 2)
    check([51] * 180, 180)
    check([26] * 180, 60)
    check([33] + [40] * 89 + [61] * 90, 135)
    check([6, 4, 5, 5], 2, 10)
    triples = Random(8873)
    values = []
    for _ in range(60):
        a = triples.randint(25, 49)
        b = triples.randint(25, 75 - a)
        values.extend([a, b, 100 - a - b])
    triples.shuffle(values)
    check(values, 60)
    generator = Random(20261024)
    timings = []
    for _ in range(120):
        values = [generator.randint(1, 100) for _ in range(generator.randint(0, 180))]
        start = perf_counter()
        check(values)
        timings.append(perf_counter() - start)
    print("130 self-tests passed; max runtime %.6f s" % max(timings))

"""Deterministic bin packing using best fit, subset sums, and bin completion.

The constructive portfolio preserves an immediately usable packing. A bounded
bin-completion search then tries smaller bin counts. Integer subset-sum tables
enumerate complete bin patterns, with equal weights handled as counts. Search
limits are operation counts, so the returned packing is deterministic.
"""

def solve(items, capacity=100):
    """Return bins containing original item indices; never mutate ``items``."""
    n = len(items)
    if not n:
        return []
    order = sorted(range(n), key=lambda i: (-items[i], i))
    total = sum(items)
    lower = (total + capacity - 1) // capacity

    # When three items cannot share a bin, sorted pairing is optimal.
    if n < 3 or sum(items[i] for i in order[-3:]) > capacity:
        result = []
        lo, hi = 0, n - 1
        while lo <= hi:
            current = [order[lo]]
            if lo < hi and items[order[lo]] + items[order[hi]] <= capacity:
                current.append(order[hi])
                hi -= 1
            lo += 1
            result.append(current)
        return result

    def best_fit(sequence):
        bins, free = [], []
        for i in sequence:
            w = items[i]
            position = -1
            best_space = capacity + 1
            for j, space in enumerate(free):
                if w <= space < best_space:
                    best_space = space
                    position = j
            if position < 0:
                bins.append([i])
                free.append(capacity - w)
            else:
                bins[position].append(i)
                free[position] -= w
        return bins

    best = best_fit(order)
    if len(best) == lower:
        return best

    # Items at least w can occupy at most capacity // w places in a bin.
    for count, i in enumerate(order, 1):
        places = capacity // items[i]
        lower = max(lower, (count + places - 1) // places)
    if len(best) == lower:
        return best

    # The L2 bound excludes tiny items that cannot enter the largest bins.
    for threshold in range(1, capacity // 2 + 1):
        large = medium = medium_sum = small_sum = 0
        for w in items:
            if w > capacity - threshold:
                large += 1
            elif 2 * w > capacity:
                medium += 1
                medium_sum += w
            elif w >= threshold:
                small_sum += w
        uncovered = max(0, small_sum - (medium * capacity - medium_sum))
        bound = large + medium + (uncovered + capacity - 1) // capacity
        if bound > lower:
            lower = bound
    if len(best) == lower:
        return best

    def subset_pack(mode):
        remaining = order[:]
        result = []
        while remaining:
            anchor = remaining.pop(0)
            room = capacity - items[anchor]
            if mode == 1:
                sequence = remaining[::-1]
            elif mode == 2:
                sequence = remaining[::2] + remaining[1::2]
            else:
                sequence = remaining
            sequence = [i for i in sequence if items[i] <= room]
            reachable = 1
            history = []
            mask = (1 << (room + 1)) - 1
            for i in sequence:
                history.append(reachable)
                reachable = (reachable | (reachable << items[i])) & mask
                if (reachable >> room) & 1:
                    break
            sequence = sequence[:len(history)]
            target = reachable.bit_length() - 1
            chosen = {anchor}
            current = [anchor]
            for pos in range(len(sequence) - 1, -1, -1):
                if not (history[pos] >> target) & 1:
                    i = sequence[pos]
                    chosen.add(i)
                    current.append(i)
                    target -= items[i]
            remaining = [i for i in remaining if i not in chosen]
            result.append(current)
        return result

    for mode in range(3):
        candidate = subset_pack(mode)
        if len(candidate) < len(best):
            best = candidate
            if len(best) == lower:
                return best

    # Work counts bound even pathological instances without clock dependence.
    weights = sorted(set(items), reverse=True)
    counts = [0] * len(weights)
    location = {w: j for j, w in enumerate(weights)}
    for w in items:
        counts[location[w]] += 1
    original_counts = counts[:]
    work = 0
    limit = 60000
    exhausted = False
    failed = set()

    def complete(bins_left, remaining_total, remaining_count):
        nonlocal work, exhausted
        work += 1
        if work >= limit:
            exhausted = True
            return None
        if not remaining_count:
            return []
        if remaining_total <= capacity:
            return [[(j, count) for j, count in enumerate(counts) if count]]
        if bins_left <= 1:
            return None
        if remaining_count <= bins_left:
            return [[(j, 1)] for j, count in enumerate(counts) for _ in range(count)]
        state = (bins_left, tuple(counts))
        if state in failed:
            return None
        first = next(j for j, count in enumerate(counts) if count)
        if sum(counts[j] for j in range(first, len(weights)) if 2 * weights[j] > capacity) > bins_left:
            failed.add(state)
            return None
        counts[first] -= 1
        anchor = weights[first]
        room = capacity - anchor
        active = [j for j in range(first, len(weights)) if counts[j] and weights[j] <= room]
        suffix = [1] * (len(active) + 1)
        mask = (1 << (room + 1)) - 1
        for p in range(len(active) - 1, -1, -1):
            j = active[p]
            reachable = suffix[p + 1]
            shifted = reachable
            for _ in range(min(counts[j], room // weights[j])):
                shifted <<= weights[j]
                reachable |= shifted
            suffix[p] = reachable & mask
        # Bin slack cannot exceed the unused space across all remaining bins.
        minimum = max(0, remaining_total - (bins_left - 1) * capacity - anchor)
        result = None
        for packed in range(room, minimum - 1, -1):
            if not (suffix[0] >> packed) & 1:
                continue
            # Explicit pattern stack keeps Python recursion proportional to bins.
            stack = [(0, packed, 0, ())]
            while stack:
                work += 1
                if work >= limit:
                    exhausted = True
                    break
                p, target, selected, pattern = stack.pop()
                if target == 0:
                    for j, take in pattern:
                        counts[j] -= take
                    slack = capacity - anchor - packed
                    if not slack or not any(count and w <= slack
                                            for w, count in zip(weights, counts)):
                        tail = complete(bins_left - 1, remaining_total - anchor - packed,
                                        remaining_count - 1 - selected)
                        if tail is not None:
                            result = [[(first, 1)] + list(pattern)] + tail
                    for j, take in pattern:
                        counts[j] += take
                    if result is not None or exhausted:
                        break
                    continue
                if p == len(active) or not (suffix[p] >> target) & 1:
                    continue
                j = active[p]
                w = weights[j]
                maximum = min(counts[j], target // w)
                for take in range(maximum + 1):
                    rest = target - take * w
                    if (suffix[p + 1] >> rest) & 1:
                        next_pattern = pattern + ((j, take),) if take else pattern
                        stack.append((p + 1, rest, selected + take, next_pattern))
            if result is not None or exhausted:
                break
        counts[first] += 1
        if result is None and not exhausted:
            failed.add(state)
        return result

    for target_bins in range(len(best) - 1, lower - 1, -1):
        counts[:] = original_counts
        patterns = complete(target_bins, total, n)
        if patterns is None:
            break
        by_weight = [[] for _ in weights]
        for i in range(n - 1, -1, -1):
            by_weight[location[items[i]]].append(i)
        best = []
        for pattern in patterns:
            current = []
            for j, count in pattern:
                for _ in range(count):
                    current.append(by_weight[j].pop())
            best.append(current)
    return best


if __name__ == '__main__':
    import random
    import time

    def check(values, capacity=100):
        result = solve(values, capacity)
        assert sorted(i for group in result for i in group) == list(range(len(values)))
        assert all(group and sum(values[i] for i in group) <= capacity for group in result)
        assert result == solve(values, capacity)
        return len(result)

    assert check([]) == 0
    assert check([100, 1, 99, 50, 50]) == 3
    assert check([6, 5, 3, 2, 2, 2], 10) == 2
    assert check([51] * 180) == 180
    assert check([1] * 180) == 2
    assert check([26] * 180) == 60
    assert check([33] + [40] * 89 + [61] * 90) == 135
    frequency = [12, 15, 11, 12, 7, 10, 7, 13, 5, 10, 10, 8, 6,
                 2, 4, 7, 3, 2, 3, 3, 5, 4, 3, 1, 2]
    partition = [w for w, count in zip(range(25, 50), frequency) for _ in range(count)]
    assert check(partition) == 55
    rng = random.Random(712093)
    started = time.perf_counter()
    for _ in range(80):
        check([rng.randint(1, 100) for _ in range(rng.randrange(181))])
    print('self-test passed: 88 cases, deterministic, %.3f s' % (time.perf_counter() - started))