Submission #1445292

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> a(n, std::vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> a[i][j];
            a[i][j]--;
        }
    }

    int ok = n;
    int ng = 0;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;

        std::vector<int> cnt(m);
        std::vector<bool> used(m, true);

        auto setval = [&]() {
            for (int i = 0; i < m; i++) {
                cnt[i] = 0;
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (used[a[i][j]]) {
                        cnt[a[i][j]]++;
                        break;
                    }
                }
            }
        };

        setval();

        while (true) {
            int pos = -1;
            for (int i = 0; i < m; i++) {
                if (cnt[i] > mid) {
                    pos = i;
                    break;
                }
            }
            if (pos == -1) break;
            used[pos] = false;
            setval();
        }

        if (std::count(used.begin(), used.end(), true) != 0) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    std::cout << ok << std::endl;
}

Submission Info

Judge Result