oj.uz

Submission #548074

# Submission time Handle Problem Language Result Execution time Memory
548074 2022-04-12T10:44:10 Z Antekb The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 324 KB 
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > rot(vector<vector<int> > &V){
    vector<vector<int> > ans(V[0].size(), vector<int>(V.size()));
    for(int i=0; i<V.size(); i++){
        for(int j=0; j<V[0].size(); j++){
            ans[V[0].size()-1-j][i]=V[i][j];
        }
    }
    return ans;
}
bool solve(vector<vector<int> > &V, int m, int M){
    auto V2=V;
    for(auto &i:V2){
        for(int &j:i){
            //cout<<j<<"a";
            j=int(j>=M)-int(j<=m);
            //cout<<j<<" ";
        }
        //cout<<"\n";
    }
    //cout<<m<<" "<<M<<"\n";
    for(int i=0; i<V.size(); i++){
        for(int j=0; j<V[0].size(); j++){
            int k=0;
            if(i){
                k=max(k, V2[i-1][j]);
            }
            if(j){
                k=max(k, V2[i][j-1]);
            }
            k=max(k, V2[i][j]);
            if(k==1 && V2[i][j]==-1){
                return 0;
            }
            V2[i][j]=k;
        }
    }
    //cout<<"+\n";
    return 1;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int h, w;
    cin>>h>>w;
   // swap(h, w);
    vector<vector<int> > V[4];
    V[0].resize(h, vector<int>(w));
    int m=1e9, M=0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            int x;
            cin>>x;
            V[0][i][j]=x;
            M=max(M, x);
            m=min(m, x);
        }
    }
    for(int i=0; i<3; i++)V[i+1]=rot(V[i]);
    int l=0, r=1e9;
    while(l<r){
        int d=(l+r)>>1;
        //cout<<d<<"\n";
        bool b=0;
        for(int i=0; i<4; i++)b|=solve(V[i],M-d, m+d);
        if(b)r=d;
        else l=d+1;
    }
    cout<<l-1;
}

Compilation message

joioi.cpp: In function 'std::vector<std::vector<int> > rot(std::vector<std::vector<int> >&)':
joioi.cpp:5:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~
joioi.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |         for(int j=0; j<V[0].size(); j++){
      |                      ~^~~~~~~~~~~~
joioi.cpp: In function 'bool solve(std::vector<std::vector<int> >&, int, int)':
joioi.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~
joioi.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int j=0; j<V[0].size(); j++){
      |                      ~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -