oj.uz

Submission #1109937

# Submission time Handle Problem Language Result Execution time Memory
1109937 2024-11-08T07:27:11 Z ljtunas The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 1250 ms 70724 KB 
// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v)    memset(h, v, sizeof h)
#define Forv(i, a)     for(auto& i : a)
#define For(i, a, b)   for(int i = a; i <= b; ++i)
#define Ford(i, a, b)  for(int i = a; i >= b; --i)
#define c_bit(i)     __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1LL)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
using namespace std;
namespace std {
    template <typename T, int D>
    struct _vector : public vector <_vector <T, D - 1>> {
        static_assert(D >= 1, "Dimension must be positive!");
        template <typename... Args>
        _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
    };
    template <typename T> struct _vector <T, 1> : public vector <T> {
        _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
    };
    template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
    template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 2e3 + 5;
const  ll  mod = 1e9 + 7;
const  ll   oo = 1e18;

//#define int long long

int n, m, mx, mn = inf; vector<vector<int>> a, b;
bool vs[MAXN][MAXN];
bool check(int val){
    For(i, 0, n - 1){
        For(j, 0, m - 1){
            b[i][j] = 0;
            if(a[i][j] <= mn + val) b[i][j] |= 1;
            if(a[i][j] >= mx - val) b[i][j] |= 2;
            if(b[i][j] == 0) return false;
        }
    }
//    cerr << '*';
    For(t, 1, 2){
        bool ok = true;
        int len = m - 1;
        For(i, 0, n - 1){
            int st = m, ed = -1;
            For(j, 0, m - 1) if(b[i][j] == t) ed = j;
            Ford(j, m - 1, 0) if(b[i][j] == (t ^ 3)) st = j;
            minimize(len, st - 1);
            if(len < ed) ok = false;
        }
        if(ok) return true;
        ok = true;
        len = m - 1;
        Ford(i, n - 1, 0){
            int st = m, ed = -1;
            For(j, 0, m - 1) if(b[i][j] == t) ed = j;
            Ford(j, m - 1, 0) if(b[i][j] == (t ^ 3)) st = j;
            minimize(len, st - 1);
            if(len < ed) ok = false;
        }
        if(ok) return true;
    }
    return false;
}

void Solve() {
    cin >> n >> m;
    a.assign(n, vector<int>(m, 0)), b.assign(n, vector<int>(m, 0));
    For(i, 0, n - 1) For(j, 0, m - 1) cin >> a[i][j], minimize(mn, a[i][j]), maximize(mx, a[i][j]);
     int l = -1, r = inf;
    while(r - l > 1){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << r << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("JOI17_joioi.inp", "r")) {
        freopen("JOI17_joioi.inp", "r", stdin);
        freopen("JOI17_joioi.out", "w", stdout);
    }

    int t = 1;
//    cin >> t;

    for (int test = 1; test <= t; test++) {
        Solve();
    }
    return 0;
}

Compilation message

joioi.cpp: In function 'void Solve()':
joioi.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~
joioi.cpp: In function 'int32_t main()':
joioi.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("JOI17_joioi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("JOI17_joioi.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 472 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 472 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 8 ms 848 KB Output is correct
17 Correct 9 ms 848 KB Output is correct
18 Correct 7 ms 848 KB Output is correct
19 Correct 10 ms 848 KB Output is correct
20 Correct 10 ms 848 KB Output is correct
21 Correct 12 ms 1192 KB Output is correct
22 Correct 8 ms 1104 KB Output is correct
23 Correct 13 ms 1104 KB Output is correct
24 Correct 6 ms 848 KB Output is correct
25 Correct 14 ms 1188 KB Output is correct
26 Correct 11 ms 1272 KB Output is correct
27 Correct 12 ms 1192 KB Output is correct
28 Correct 11 ms 1104 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 472 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 8 ms 848 KB Output is correct
17 Correct 9 ms 848 KB Output is correct
18 Correct 7 ms 848 KB Output is correct
19 Correct 10 ms 848 KB Output is correct
20 Correct 10 ms 848 KB Output is correct
21 Correct 12 ms 1192 KB Output is correct
22 Correct 8 ms 1104 KB Output is correct
23 Correct 13 ms 1104 KB Output is correct
24 Correct 6 ms 848 KB Output is correct
25 Correct 14 ms 1188 KB Output is correct
26 Correct 11 ms 1272 KB Output is correct
27 Correct 12 ms 1192 KB Output is correct
28 Correct 11 ms 1104 KB Output is correct
29 Correct 895 ms 52380 KB Output is correct
30 Correct 875 ms 51276 KB Output is correct
31 Correct 908 ms 54808 KB Output is correct
32 Correct 892 ms 54984 KB Output is correct
33 Correct 481 ms 47932 KB Output is correct
34 Correct 988 ms 55100 KB Output is correct
35 Correct 1064 ms 70472 KB Output is correct
36 Correct 671 ms 61512 KB Output is correct
37 Correct 1250 ms 70724 KB Output is correct