Submission #103795

#	Time	Username	Problem	Language	Result	Execution time	Memory
103795		RockyB	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	2 ms	384 KiB

joioi

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)2000 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m;
int a[N][N];

int mn = inf, mx = -inf;
bool check(int k) {
	int r = 0;
	rep(i, 1, n) {
		r = 0;
		per(j, m, 1) {
			if (!(a[i][j] <= mn + k)) r = max(r, j);
			if (!(a[i][j] >= mx - k)) {
				if (j <= r) return 0;
			}
		}	
	}
	return 1;
}
int ans;
int solve() {
	int l = 0, r = ans - 1, res = ans;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	return res;
}
void rows() {
	rep(i, 1, n / 2) {
		rep(j, 1, m) swap(a[i][j], a[n - i + 1][j]);
	}
}
void cols() {
	rep(i, 1, m / 2) {
		rep(j, 1, n) {
			swap(a[j][i], a[j][m - i + 1]);
		}
	}
}

int get_int() {
	char x = getchar();
	while (!isdigit(x)) x = getchar();
	int res = 0;
	while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
	return res;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	n = get_int(), m = get_int();
	rep(i, 1, n) rep(j, 1, m) {
		a[i][j] = get_int();
		mn = min(mn, a[i][j]);
		mx = max(mx, a[i][j]);
	}
	ans = mx - mn;
	ans = min(ans, solve());
	cols();
	ans = min(ans, solve());
	rows();
	ans = min(ans, solve());
	cols();
	ans = min(ans, solve());
	cout << ans;
	ioi
}

Compilation message (stderr)

joioi.cpp: In function 'int solve()':
joioi.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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