oj.uz

Submission #481370

# Submission time Handle Problem Language Result Execution time Memory
481370 2021-10-20T13:50:42 Z Lobo The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 1327 ms 25684 KB 
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 2002

ii n, m, a[maxn][maxn];
pair<ii,ii> p[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> m;

    ii mn = INFii;
    ii mx = 0;

    for(ii i = 1; i <= n; i++) {
        for(ii j = 1; j <= m; j++) {
            cin >> a[i][j];
            mn = min(mn,a[i][j]);
            mx = max(mx,a[i][j]);
        }
    }

    if(mn == mx) {
        cout << 0 << endl;
        return 0;
    }

    // com minimo na esquerda:

    ii l = 0;
    ii r = 1e9+1;
    ii ans1;

    while(l <= r) {
        ii mid = (l+r)/2;
        for(ii i = 1; i <= n; i++) {
            p[i].fr = 0;
            p[i].sc = m+1;
        }

        
        for(ii i = 1; i <= n; i++) {
            for(ii j = 1; j <= m; j++) {
                if(abs(a[i][j]-mn) > mid) {
                    p[i].sc = min(p[i].sc,j-1);
                }

                if(abs(a[i][j]-mx) > mid) {
                    p[i].fr = max(p[i].fr,j);
                }
            }
        }

        //ver se ta crescente/decrescente
        ii actc = 0; bool okc = 1;
        ii actd = m+1; bool okd = 1;

        for(ii i = 1; i <= n; i++) {
            actc = max(actc,p[i].fr);
            if(actc > p[i].sc || p[i].fr > p[i].sc) okc = 0;

            actd = min(actd,p[i].sc);
            if(actd < p[i].fr || p[i].fr > p[i].sc) okd = 0;
        }

        if(okc || okd) {
            //se deu bom com esse (l+r)/2 quero abaixar o (l+r)/2
            ans1 = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }

    //com mx na esquerda

    l = 0;
    r = 1e9+1;
    ii ans2;


    while(l <= r) {
        ii mid = (l+r)/2;
        for(ii i = 1; i <= n; i++) {
            p[i].fr = 0;
            p[i].sc = m+1;
        }

        
        for(ii i = 1; i <= n; i++) {
            for(ii j = 1; j <= m; j++) {
                if(abs(a[i][j]-mn) > mid) {
                    p[i].fr = max(p[i].fr,j);
                }

                if(abs(a[i][j]-mx) > mid) {
                    p[i].sc = min(p[i].sc,j-1);
                }
            }
        }

        //ver se ta crescente/decrescente
        ii actc = 0; bool okc = 1;
        ii actd = m+1; bool okd = 1;

        for(ii i = 1; i <= n; i++) {
            actc = max(actc,p[i].fr);
            if(actc > p[i].sc || p[i].fr > p[i].sc) okc = 0;

            actd = min(actd,p[i].sc);
            if(actd < p[i].fr || p[i].fr > p[i].sc) okd = 0;
        }

        if(okc || okd) {
            //se deu bom com esse (l+r)/2 quero abaixar o (l+r)/2
            ans2 = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }

    cout << min(ans1,ans2) << endl;

}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:98:8: warning: 'ans2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     ii ans2;
      |        ^~~~
joioi.cpp:50:8: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     ii ans1;
      |        ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 8 ms 1344 KB Output is correct
17 Correct 9 ms 1484 KB Output is correct
18 Correct 12 ms 1484 KB Output is correct
19 Correct 11 ms 1468 KB Output is correct
20 Correct 11 ms 1408 KB Output is correct
21 Correct 13 ms 1612 KB Output is correct
22 Correct 15 ms 1612 KB Output is correct
23 Correct 14 ms 1612 KB Output is correct
24 Correct 12 ms 1480 KB Output is correct
25 Correct 16 ms 1612 KB Output is correct
26 Correct 11 ms 1612 KB Output is correct
27 Correct 11 ms 1668 KB Output is correct
28 Correct 13 ms 1612 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 8 ms 1344 KB Output is correct
17 Correct 9 ms 1484 KB Output is correct
18 Correct 12 ms 1484 KB Output is correct
19 Correct 11 ms 1468 KB Output is correct
20 Correct 11 ms 1408 KB Output is correct
21 Correct 13 ms 1612 KB Output is correct
22 Correct 15 ms 1612 KB Output is correct
23 Correct 14 ms 1612 KB Output is correct
24 Correct 12 ms 1480 KB Output is correct
25 Correct 16 ms 1612 KB Output is correct
26 Correct 11 ms 1612 KB Output is correct
27 Correct 11 ms 1668 KB Output is correct
28 Correct 13 ms 1612 KB Output is correct
29 Correct 918 ms 15616 KB Output is correct
30 Correct 961 ms 16188 KB Output is correct
31 Correct 1123 ms 19524 KB Output is correct
32 Correct 934 ms 19532 KB Output is correct
33 Correct 850 ms 14276 KB Output is correct
34 Correct 1029 ms 19396 KB Output is correct
35 Correct 1031 ms 25628 KB Output is correct
36 Correct 1042 ms 23020 KB Output is correct
37 Correct 1327 ms 25684 KB Output is correct