#include<bits/stdc++.h>
using namespace std;
int haha[2001][2001];
int n,m;
bool check(int a) {
int x = -1;
vector<int> sm0(n,INT_MAX);
vector<int> big0(n,0);
vector<int> sm1(n,INT_MAX);
vector<int> big1(n,0);
for(int i = 0; i < n; i++) {
int l = -1;
for(int j = 0; j < m; j++) {
if(haha[i][j] != -1) {
if(haha[i][j] == 0) {
big0[i] = max(big0[i],j+1);
sm0[i] = min(sm0[i],j+1);
}
else {
big1[i] = max(big1[i],j+1);
sm1[i] = min(sm1[i],j+1);
}
}
}
}
int p = -1;
for(int i = 0; i < n; i++) {
int c = -1;
if(sm0[i] == INT_MAX || sm1[i] == INT_MAX) {
continue;
}
if(sm0[i] > big1[i]) {
c = 1;
}
else if(big0[i] < sm1[i]) {
c = 0;
}
else {
return false;
}
if(p != -1 && c != p) {
return false;
}
p = c;
}
if(p == -1) {
return true;
}
x = m;
for(int i = 0; i < n; i++) {
int l,r;
if(p == 0) {
l = big0[i];
r = min(m,sm1[i]-1);
}
else {
l = big1[i];
r = min(m,sm0[i]-1);
}
if(x < l) {
break;
}
x = min(x,r);
if(i == n-1) {
return true;
}
}
x = 0;
for(int i = 0; i < n; i++) {
int l,r;
if(p == 0) {
l = big0[i];
r = min(m,sm1[i]-1);
}
else {
l = big1[i];
r = min(m,sm0[i]-1);
}
if(x > r) {
break;
}
x = max(x,l);
if(i == n-1) {
return true;
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
int a;
vector<pair<int,pair<int,int>>> bruh(0);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> a;
bruh.push_back({a,{i,j}});
}
}
sort(bruh.begin(),bruh.end());
int sm = bruh[0].first,big = bruh[n*m-1].first;
int l = 0,r = 1e9;
while(l < r) {
int mid = (l+r)/2;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
haha[i][j] = -1;
}
}
haha[bruh[0].second.first][bruh[0].second.second] = 0;
for(int i = 1; i < bruh.size(); i++) {
if(big-bruh[i].first > mid) {
haha[bruh[i].second.first][bruh[i].second.second] = 0;
}
}
bool yeah = true;
for(int i = 0; i < bruh.size(); i++) {
if(bruh[i].first-sm > mid) {
if(haha[bruh[i].second.first][bruh[i].second.second] != -1) {
yeah = false;
}
haha[bruh[i].second.first][bruh[i].second.second] = 1;
}
}
if(yeah && check(mid)) {
r = mid;
}
else {
l = mid+1;
}
}
cout << l;
return 0;
}
Compilation message
joioi.cpp: In function 'bool check(int)':
joioi.cpp:14:13: warning: unused variable 'l' [-Wunused-variable]
14 | int l = -1;
| ^
joioi.cpp: In function 'int main()':
joioi.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i = 1; i < bruh.size(); i++) {
| ~~^~~~~~~~~~~~~
joioi.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i = 0; i < bruh.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
