oj.uz

Submission #692370

# Submission time Handle Problem Language Result Execution time Memory
692370 2023-02-01T11:20:42 Z Paul_Liao_1457 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2982 ms 213928 KB 
//記得跳題
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
 
#define ll long long
#define LL __int128_t
#define DB double
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define INF (ll)(2e9)
#define MOD (ll)(1e9+7)
#define F first
#define S second
#define endl "\n"
#define AC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
 
struct func{
    bool operator()(const int &x, const int &y) const{
        return x<y;
    }
};
 
template<class T> using PQ=priority_queue<T,vector<T>,func>;
 
void file(){
    freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
    freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
}

int a[9][2005][2005],ih,iw,pre[2][2005][2005],suf[2][2005][2005];

int h,w;

void turn(int t){
    FOR(i,1,w+1){
        FOR(j,1,h+1){
            a[t][i][j]=a[t-1][j][w-i+1];
        }
    }
    swap(h,w);
}

void flap(int t){
    FOR(i,1,h+1){
        FOR(j,1,w+1){
            a[t][i][j]=a[t-1][h-i+1][w-j+1];
        }
    }
}

int now=0;
int minn=INF;

bool check(int k){
    //cout<<"k="<<k<<endl;
    h=ih; w=iw;
    now=0;
    FOR(i,1,8){
        bool ok=1;
        if(now==4) now++;
        FOR(i,1,h+1){
            pre[1][i][0]=0;
            suf[1][i][w+1]=0;
            pre[0][i][0]=INF;
            suf[0][i][w+1]=INF;
            FOR(j,1,w+1){
                pre[0][i][j]=min(pre[0][i][j-1],a[now][i][j]);
                pre[1][i][j]=max(pre[1][i][j-1],a[now][i][j]);
                //cout<<"pre["<<i<<"]["<<j<<"]="<<pre[1][i][j]<<endl;
            }
            REP(j,w,1){
                suf[0][i][j]=min(suf[0][i][j+1],a[now][i][j]);
                suf[1][i][j]=max(suf[1][i][j+1],a[now][i][j]);
                //cout<<"suf["<<i<<"]["<<j<<"]="<<suf[1][i][j]<<endl;
            }
        }
        int tmp=w,mi=INF,mx=0,lm=INF;
        FOR(x,1,h+1){
            while(tmp>0&&pre[1][x][tmp]>minn+k){
                tmp--;
            }
            lm=min(lm,pre[0][x][tmp]);
            mi=min(mi,suf[0][x][tmp+1]);
            mx=max(mx,suf[1][x][tmp+1]);
            //cout<<"mx="<<mx<<" mi="<<mi<<" lm="<<lm<<" tmp="<<tmp<<endl;
            if(mx-mi>k){
                ok=0; break;
            }
        }
        if(lm!=minn){
            ok=0;
        }
        if(ok){
            return 1;
        }
        swap(h,w); now++;
    }
    return 0;
}

signed main(){
    AC;
    cin>>h>>w; ih=h; iw=w;
    FOR(i,1,h+1)FOR(j,1,w+1){
        cin>>a[0][i][j]; minn=min(minn,a[0][i][j]);
    }
    
    int cur=0;
    FOR(i,1,8){
        cur++;
        if(i==4){
            cur++;
            flap(cur);
        }
        turn(cur);
    }
    
    int l=0,r=1e9+1,ans=INF;
    
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)){
            r=mid; ans=min(ans,mid);
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

 
/*
 4 5
 1 2 4 4
 1 3 2 1
 4 3 1 2
 4 1 6 1
 2 4 2 5
 
 */

Compilation message

joioi.cpp: In function 'void file()':
joioi.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 4 ms 7892 KB Output is correct
16 Correct 12 ms 11556 KB Output is correct
17 Correct 20 ms 11820 KB Output is correct
18 Correct 20 ms 11888 KB Output is correct
19 Correct 21 ms 11860 KB Output is correct
20 Correct 20 ms 11512 KB Output is correct
21 Correct 25 ms 11924 KB Output is correct
22 Correct 28 ms 11860 KB Output is correct
23 Correct 22 ms 11876 KB Output is correct
24 Correct 21 ms 11512 KB Output is correct
25 Correct 24 ms 11924 KB Output is correct
26 Correct 27 ms 11860 KB Output is correct
27 Correct 28 ms 11860 KB Output is correct
28 Correct 31 ms 11908 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 4 ms 7892 KB Output is correct
16 Correct 12 ms 11556 KB Output is correct
17 Correct 20 ms 11820 KB Output is correct
18 Correct 20 ms 11888 KB Output is correct
19 Correct 21 ms 11860 KB Output is correct
20 Correct 20 ms 11512 KB Output is correct
21 Correct 25 ms 11924 KB Output is correct
22 Correct 28 ms 11860 KB Output is correct
23 Correct 22 ms 11876 KB Output is correct
24 Correct 21 ms 11512 KB Output is correct
25 Correct 24 ms 11924 KB Output is correct
26 Correct 27 ms 11860 KB Output is correct
27 Correct 28 ms 11860 KB Output is correct
28 Correct 31 ms 11908 KB Output is correct
29 Correct 1588 ms 186372 KB Output is correct
30 Correct 1570 ms 184152 KB Output is correct
31 Correct 1846 ms 188612 KB Output is correct
32 Correct 1773 ms 188724 KB Output is correct
33 Correct 1397 ms 182116 KB Output is correct
34 Correct 1936 ms 188728 KB Output is correct
35 Correct 2982 ms 188732 KB Output is correct
36 Correct 1934 ms 213928 KB Output is correct
37 Correct 2435 ms 213208 KB Output is correct