Submission #1025046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025046		phong	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1923 ms	133332 KiB

joioi

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define ll long long
//#define int long long
const int nmax = 2e3 + 5;
const int lg = 18;
const int base = 311;
const int M = 5e6;
const ll oo = 1e9 + 1;
const int mod = 987654321;
#define fi first
#define se second
#define endl "\n"
#define debug(a, m) for(int j = 1; j <= n; ++j) cout << a[j] << ' ';cout << endl;
#define pii pair<ll, int>

using namespace std;

int n, m, a[nmax][nmax], mx = -1;
int pos[nmax], pre[nmax][nmax][2], suf[nmax][nmax][2];
int tmp[nmax][nmax];

bool check(int mid){
    for(int k = 1; k <= 4; ++k){
        for(int i = 1; i <= n; ++i){
            pre[i][0][0] = suf[i][m + 1][0] = oo;
            pre[i][0][1] = suf[i][m + 1][1] = -oo;
            for(int j = 1; j <= m; ++j){
                pre[i][j][0] = min(pre[i][j - 1][0], a[i][j]);
                pre[i][j][1] = max(pre[i][j - 1][1], a[i][j]);
            }
            for(int j = m; j >= 1; --j){
                suf[i][j][0] = min(suf[i][j + 1][0], a[i][j]);
                suf[i][j][1] = max(suf[i][j + 1][1], a[i][j]);
            }
        }
        for(int i = 1; i <= n; ++i){
            pos[i] = -1;
            for(int j = 1; j <= m; ++j){
                if(mx - mid > a[i][j]){
                    pos[i] = j;
                }
            }
//            cout << pos[i] << ' ';
        }
//        return 0;
        int ma_1 = -oo, mi_1 = oo, ma_2 = -oo, mi_2 = oo, idx = 0;
        for(int i = 1; i <= n; ++i){
            idx = max(idx, pos[i]);
            ma_1 = max(ma_1, pre[i][idx][1]);
            ma_2 = max(ma_2, suf[i][idx + 1][1]);
            mi_1 = min(mi_1, pre[i][idx][0]);
            mi_2 = min(mi_2, suf[i][idx + 1][0]);
        }
        if(ma_1 - mi_1 <= mid && ma_2 - mi_2 <= mid) return 1;

        ma_1 = -oo, mi_1 = oo, ma_2 = -oo, mi_2 = oo, idx = 0;
        for(int i = n; i >= 1; --i){
            idx = max(idx, pos[i]);
            ma_1 = max(ma_1, pre[i][idx][1]);
            ma_2 = max(ma_2, suf[i][idx + 1][1]);
            mi_1 = min(mi_1, pre[i][idx][0]);
            mi_2 = min(mi_2, suf[i][idx + 1][0]);
        }
//        cout <<ma_1 << ' ' <<mi_1 << ' ' << ma_2 << ' ' << mi_2 << ' ' << mi;
//        return 0;
        if(ma_1 - mi_1 <= mid && ma_2 - mi_2 <= mid) return 1;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                tmp[j][n - i + 1] = a[i][j];
            }
        }
        swap(n, m);
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                a[i][j] = tmp[i][j];
//                cout << a[i][j] << ' ';
            }
//            cout << endl;
        }
//        return 0;
    }
    return 0;

}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i<= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
        }
    }
//    vector<int> nen;
//    for(int i = 1; i <= n; ++i){
//        for(int j = 1; j <= m; ++j){
//            nen.push_back(mx - a[i][j]);
//        }
//    }
//    sort(nen.begin(), nen.end());
//    nen.erase(unique(nen.begin(), nen.end()), nen.end());

//    cout <<
//check(11);
    int l = 1, r= 1e9, kq = -1;
    while(l <= r){
        int mid = r + l >> 1;
        if(check(mid)){
            kq = mid;
            r = mid - 1;
        }
        else l= mid + 1;
    }
    cout << kq;
//    cout << check(11);
//    for(int i =1; i <= 100; ++i){
//        cout << i << ' ' << check(i) << endl;
//    }
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

*/

Compilation message (stderr)

joioi.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main(){
      | ^~~~
joioi.cpp: In function 'int main()':
joioi.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = r + l >> 1;
      |                   ~~^~~

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