/*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];
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int mn = 1e9, mx = 0;
int color[N][N];
bool taken[N][N];
bool check(int lim, int piv) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
color[i][j] = 0;
if (mn + lim >= a[i][j]) color[i][j]++;
if (mx - lim <= a[i][j]) color[i][j] += 2;
taken[i][j] = false;
}
}
int preLen = 0;
for (int i = 1; i <= n; i++) {
int nxlen = 0;
if (i == 1) {
if (bit(color[1][1], piv) == 0) return false;
taken[1][1] = true;
for (int j = 2; j <= m; j++) {
if (bit(color[i][j], piv) == 0)
break;
nxlen = j;
taken[i][j] = true;
}
}
else {
if (bit(color[i][1], piv) == 1) {
taken[i][1] = true;
for (int j = 2; j <= preLen; j++) {
if (bit(color[i][j], piv) == 0)
break;
nxlen = j; taken[i][j] = true;
}
}
}
preLen = nxlen;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!taken[i][j] && bit(color[i][j], (1 - piv)) == 0) return false;
}
}
return true;
}
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]);
mn = min(mn, a[i][j]); mx = max(mx, a[i][j]);
}
}
int l = 0, r = 1e9;
while (l != r) {
int mid = (l + r) / 2;
if (check(mid, 0) || check(mid, 1)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
Compilation message
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:111: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:114:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i][j]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
37348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
37348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
37348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
37348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
37348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
37348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
