[AGC061D] Almost Multiplication Table

人类智慧。

答案显然具有可二分性，考虑如何check。

我们使用调整法，不妨设 \(x_n<y_m\) （反着做同理），一开始我们令 \(x_i=1,y_i=+\infty\)。每次我们期望让 \(x\) 不断变大，\(y\) 不断变小，不断将它们调整到当前的上下界。具体的，每次令 \(x_i=\max \{x_i, \max \lceil {a_{i,j}-k\over y_j} \rceil\}, y_i = \min \{y_i, \min \lfloor {a_{i,j}+k\over x_j} \rfloor \}\)。为了保证单调性，还需令 \(x_i=\max\{x_i,x_{i-1}+1\}\),\(y_i=\min\{y_i,y_{i+1}-1\}\)

显然在任意时刻，都存在合法的 \(x\) 大于等于当前的 \(x\)，最后一定会到一个合法解。如果当前 \(x_n>y_m\) 或 \(y_1 \le 0\) 就直接 break.

考虑它的复杂度，每个 \(x\) 至多会增加到根号值域，由于 \(n,m\) 很小，可以轻松跑过。

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 15;
 
inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f; 
}
 
typedef long long ll;
 
const ll inf = 2e9;
 
ll a[N][N], x[N], y[N];
int n, m;
 
inline ll abs_(ll a) {
	return a < 0 ? -a : a;
}
 
inline bool chk(ll k) {
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (x[i] <= 0 || y[j] <= 0 || abs_(x[i] * y[j] - a[i][j]) > k) return 0;
	return 1;
}
 
inline bool check(ll k) {
	for (int i = 1; i <= n; ++i) x[i] = 1;
	for (int i = 1; i <= m; ++i) y[i] = inf;
	y[m + 1] = inf + 1;
	while (1) {
		for (int i = 1; i <= n; ++i) {
			ll r = -1;
			for (int j = 1; j <= m; ++j)
				r = max(r, (a[i][j] - k + y[j] - 1) / y[j]);
			x[i] = max(max(x[i], x[i - 1] + 1), r);
		}
		for (int i = m; i; --i) {
			ll r = inf;
			for (int j = 1; j <= n; ++j)
				r = min(r, (a[j][i] + k) / x[j]);
			y[i] = min(min(y[i], y[i + 1] - 1), r);
		} if (chk(k)) return 1;
		if (x[n] > y[m] || y[1] <= 0) break;
	}
	for (int i = 1; i <= n; ++i) x[i] = inf;
	for (int i = 1; i <= m; ++i) y[i] = 1;
	x[n + 1] = inf + 1;
	while (1) {
		for (int i = 1; i <= m; ++i) {
			ll r = -1;
			for (int j = 1; j <= n; ++j)
				r = max(r, (a[j][i] - k + x[j] - 1) / x[j]);
			y[i] = max(max(y[i], y[i - 1] + 1), r);
		}
		for (int i = n; i; --i) {
			ll r = inf;
			for (int j = 1; j <= m; ++j)
				r = min(r, (a[i][j] + k) / y[j]);
			x[i] = min(min(x[i], x[i + 1] - 1), r);
		} if (chk(k)) return 1;
		if (y[n] > x[m] || x[1] <= 0) break;
	}
	return 0;
}
 
int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) a[i][j] = read();
	ll l = 0, r = 1e9, mid, res = r;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) r = (res = mid) - 1;
		else l = mid + 1;
	} check(res);
	printf("%lld\n", res);
	for (int i = 1; i <= n; ++i) printf("%lld ", x[i]);
	puts("");
	for (int i = 1; i <= m; ++i) printf("%lld ", y[i]);
	return 0;
}