Submission #33293

#	Time	Username	Problem	Language	Result	Execution time	Memory
33293		UncleGrandpa925	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	6 ms	21644 KiB

joioi

/*input
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

8 6
23 23 10 11 16 21 15 26
19 28 19 20 25 26 28 16
15 11 11 8 19 11 15 24
14 19 15 14 24 11 10 8
11 7 6 14 23 5 19 23
17 17 18 11 21 14 20 16
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define N 2005
#define bit(x,y) ((x>>y)&1LL)
#define show(x) cout << (#x) << ": " << x << endl;
#define ii pair<int,int>
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n, m;
int a[N][N];
bool color[N][N];
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool check(int lim) {
	memset(color, 0, sizeof(color));
	int preLen = 0;
	for (int i = 1; i <= n; i++) {
		int nxlen = 0;
		if (i == 1) {
			color[1][1] = 1;
			for (int j = 2; j <= m; j++) {
				if (abs(a[i][j] - a[i][j - 1]) > lim) {
					break;
				}
				color[i][j] = 1;
				nxlen = j;
			}
		}
		else {
			for (int j = 1; j <= preLen; j++) {
				if (abs(a[i][j] - a[i - 1][j]) > lim)
					break;
				if (j >= 2 && abs(a[i][j] - a[i][j - 1]) > lim)
					break;
				color[i][j] = 1; nxlen = j;
			}
		}
		preLen = nxlen;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = 0; k < 4; k++) {
				int ax = i + dx[k];
				int ay = j + dy[k];
				if (ax < 1 || ay < 1 || ax > n || ay > m || color[ax][ay] != color[i][j]) continue;
				if (abs(a[ax][ay] - a[i][j]) > lim) return false;
			}
		}
	}
	return true;
}

bool fullcheck(int lim) {
	if (check(lim)) return true;
	for (int i = 1; i <= n; i++) reverse(a[i] + 1, a[i] + m + 1);
	if (check(lim)) return true;
	return false;
}

signed main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	int l = 1, r = 1e9;
	while (l != r) {
		int mid = (l + r) / 2;
		if (fullcheck(mid))
			r = mid;
		else
			l = mid + 1;
	}
	printf("%d\n", l);
}

Compilation message (stderr)

joioi.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
joioi.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
joioi.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<int, int> >&)':
joioi.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
joioi.cpp: In function 'int main()':
joioi.cpp:113:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
joioi.cpp:116:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
                         ^

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