#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxN = 2e1 + 326, INF = 2e9 + 326;
int N, M, arr[maxN][maxN], narr[maxN][maxN], cnt[maxN * maxN], sz;
vector<int> lisan;
vector<pii> pos[maxN * maxN];
bool vis[maxN][maxN];
void take(int y, int x, int &mx, int &mn){
for(int i = y; i >= 0 && !vis[i][x]; i--){
for(int j = x; j >= 0 && !vis[i][j]; j--){
vis[i][j] = true;
cnt[arr[i][j]]--;
mx = max(mx, arr[i][j]);
mn = min(mn, arr[i][j]);
}
}
}
void rot(){
//(i, j) -> (j, N - 1 - i)
for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) {
narr[j][N - 1 - i] = arr[i][j];
vis[i][j] = false;
}
for(int i = 0; i < sz; i++) for(auto &[y, x] : pos[i]){
swap(y, x);
cnt[i] = 0;
x = N - 1 - x;
}
for(int i = 0; i < M; i++) for(int j = 0; j < N; j++){
arr[i][j] = narr[i][j];
cnt[arr[i][j]]++;
}
swap(N, M);
}
int main(){
ericxiao;
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
lisan.push_back(arr[i][j]);
}
}
sort(lisan.begin(), lisan.end());
sz = unique(lisan.begin(), lisan.end()) - lisan.begin();
for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){
arr[i][j] = lower_bound(lisan.begin(), lisan.begin() + sz, arr[i][j]) - lisan.begin();
cnt[arr[i][j]]++;
pos[arr[i][j]].emplace_back(i, j);
}
int ans = lisan[sz - 1] - lisan[0];
for(int jizz = 0; jizz < 4; jizz++){
//cout << "in jizz = " << jizz << endl;
int mx = -INF, mn = INF, f = 0, e = sz - 1;
for(int i = 0; i < sz; i++){
//take all of them
//
//cout << "i = " << i << ", = " << lisan[i] << endl;
for(auto [y, x] : pos[i]){
take(y, x, mx, mn);
}
for(int y = 0; y < N; y++) for(int x = 0; x < M; x++){
cout << vis[y][x] << " \n"[x == M - 1];
}
cout << endl;
while(f < sz - 1 && !cnt[f]) f++;
while(e && !cnt[e]) e--;
if(f == sz || !e) break;
ans = min(ans, max(lisan[e] - lisan[f], lisan[mx] - lisan[mn]));
//cout << "ans = " << ans << endl;
}
rot();
}
cout << ans << endl;
}
Compilation message
joioi.cpp: In function 'void rot()':
joioi.cpp:35:40: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
35 | for(int i = 0; i < sz; i++) for(auto &[y, x] : pos[i]){
| ^
joioi.cpp: In function 'int main()':
joioi.cpp:71:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | for(auto [y, x] : pos[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
