Submission #896421

#	Time	Username	Problem	Language	Result	Execution time	Memory
896421		goodspeed0208	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1212 ms	70940 KiB

joioi

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<utility>
#define int long long
#define INF 1000000000000000000
using namespace std;

int n, m;
int minn = INF, maxx = -INF;
vector<vector<int> >v;

bool check(int t) {
	int smallmax = minn + t, bigmin = maxx - t;
	// small 在下
	vector<int>smalllimit(m, 0), biglimit(m, n);
	for (int j = 0 ; j < m ; j++) {
		for (int i = n-1 ; i >= 0 ; i--) {
			if (v[i][j] > smallmax) {
				smalllimit[j] = i+1;
				break;
			}
		}
		for (int i = 0 ; i < n ; i++) {
			if (v[i][j] < bigmin) {
				biglimit[j] = i-1;
				break;
			}
		} 
	} 
	// 左 到右 下到上 
	bool can = 1;
	int last = n+1;
	for (int i = 0 ; i < m ; i++) {
		last = min(last, biglimit[i]);
		if (last + 1 < smalllimit[i]) {
			can = 0;
			break;
		}
	}
	if (can) return 1;
	can = 1;
	last = n+1;
	for (int i = m-1 ; i >= 0 ; i--) {
		last = min(last, biglimit[i]);
		if (last + 1 < smalllimit[i]) {
			can = 0;
			break;
		}
	}
	return can;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	v = vector<vector<int> >(n, vector<int>(m));
	for (int i = 0 ; i < n ; i++) {
		for (int j = 0 ; j < m ; j++) {
			cin >> v[i][j];
			if (v[i][j] < minn) minn = v[i][j];
			if (v[i][j] > maxx) maxx = v[i][j];
		}
	}
	int ans = INF;
	int l = 0, r = 1000000005, mid;
	while (l + 1 < r) {
		mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	ans = min(ans, r);
	for (int j = 0 ; j < m ; j++) {
		for (int i = 0 ; i < n/2 ; i++) {
			swap(v[i][j], v[n-i-1][j]); 
		}
	}
	l = 0, r = 1000000005, mid;
	while (l + 1 < r) {
		mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	ans = min(ans, r);
	cout << ans << "\n";
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:82:28: warning: right operand of comma operator has no effect [-Wunused-value]
   82 |  l = 0, r = 1000000005, mid;
      |                            ^

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40