oj.uz

Submission #481114

# Submission time Handle Problem Language Result Execution time Memory
481114 2021-10-19T13:47:58 Z Lobo The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 332 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 2200

ii n, m, a[maxn][maxn];
map<ii,vector<pair<ii,ii>>> val;
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];
            val[a[i][j]].pb(mp(i,j));
            mn = min(mn,a[i][j]);
            mx = max(mx,a[i][j]);
        }
    }

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

    vector<pair<pair<ii,ii>,vector<pair<ii,ii>>>> pq;

    for(auto x : val) {
        pq.pb(mp(mp(x.fr-mn,0),x.sc));
        pq.pb(mp(mp(mx-x.fr,1),x.sc));
    }

    sort(all(pq), greater<pair<pair<ii,ii>,vector<pair<ii,ii>>>>());
    // 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 = 1;
            p[i].sc = m;
        }

        for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {

            ii tp = pq[i].fr.sc;

            for(auto x : pq[i].sc) {
                if(tp == 1) { // tem que ta junto com o mn
                    p[x.fr].fr = max(p[x.fr].fr,x.sc);
                }
                else {
                    p[x.fr].sc = min(p[x.fr].sc,x.sc);
                }
            }
        }
    
        //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) okc = 0;

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

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

    //com mx na esquerda

    for(ii i = 0; i < pq.size(); i++) {
        pq[i].fr.sc^= 1;
    }

    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 = 1;
            p[i].sc = m;
        }

        for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
            ii tp = pq[i].fr.sc;

            for(auto x : pq[i].sc) {
                if(tp == 1) { // tem que ta junto com o mn
                    p[x.fr].fr = max(p[x.fr].fr,x.sc);
                }
                else {
                    p[x.fr].sc = min(p[x.fr].sc,x.sc-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) okc = 0;

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

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

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

}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:69:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
      |                       ~~^~~~~~~~~~~
joioi.cpp:107:21: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(ii i = 0; i < pq.size(); i++) {
      |                   ~~^~~~~~~~~~~
joioi.cpp:122:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
      |                       ~~^~~~~~~~~~~
joioi.cpp:113:8: warning: 'ans2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     ii ans2;
      |        ^~~~
joioi.cpp:60:8: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     ii ans1;
      |        ^~~~

Subtask #1
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 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
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 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -