http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp17Day2&pid=J

rupc2017day2J.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!
 
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}
 
inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}
 
using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;
 
struct edge { int to, cap, rev; };
 
const int MAX_V = 300;
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
 
void add_edge(int from, int to, int cap) {
    G[from].emplace_back((edge){to, cap, (int)G[to].size()});
    G[to].emplace_back((edge){from, 0, (int)G[from].size() - 1});
}
 
void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i = 0; i < G[v].size(); i++) {
            edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}
 
int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
 
int max_flow(int s, int t) {
    int flow = 0;
    for (;;) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, inf)) > 0) {
            flow += f;
        }
    }
}
 
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int n, m;
    cin >> n >> m;
    vvi h(n, vi(m));
    rep(i, n) rep(j, m) cin >> h[i][j];
 
    auto check = [&](int ma) {
        rep(v, MAX_V) G[v].clear();
 
        rep(i, n) {
            rep(j, m) {
                if (h[i][j] <= ma) {
                    add_edge(i, j + n, 1);
                }
            }
        }
 
        const int s1 = n + m;
        const int s2 = n + m + 1;
        const int t = n + m + 2;
 
        rep(i, n) {
            add_edge(s1, i, m / n);
            add_edge(s2, i, 1);
        }
 
        rep(j, m) {
            add_edge(j + n, t, 1);
        }
 
        if (max_flow(s1, t) < (m / n) * n) return false;
        return max_flow(s2, t) == m % n;
    };
 
    int l = 0, r = 1e9;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        (check(mid) ? r : l) = mid;
    }
    cout << (m % n != 0) << endl;
    cout << r << endl;
}