Submission #537397

#	Time	Username	Problem	Language	Result	Execution time	Memory
537397		79brue	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	822 ms	16128 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int arr[2002][2002];
int totalMin, totalMax;
int zero[2002][2], one[2002][2];

void flipArr(){
    for(int i=1; i<=n; i++) if(i<n+1-i){
        for(int j=0; j<2; j++){
            swap(zero[i][j], zero[n+1-i][j]);
            swap(one[i][j], one[n+1-i][j]);
        }
    }
//    for(int i=1; i<=n; i++) for(int j=0; j<2; j++){
//        if(1<=zero[i][j] && zero[i][j]<=m) zero[i][j] = m+1-zero[i][j];
//        if(1<=one[i][j] && one[i][j] <= m) one[i][j] = m+1-one[i][j];
//    }
}

void swapArr(){
    for(int i=1; i<=n; i++) for(int j=0; j<2; j++) swap(zero[i][j], one[i][j]);
}

bool solve(){
    /// 왼쪽은 0, 오른쪽은 1
    /// 경계는 i가 커질수록 단조증가
    int zeroRight = 0;
    for(int i=1; i<=n; i++){
        if(one[i][0] < zero[i][1]) return false;
        if(zeroRight >= one[i][0]) return false;
        zeroRight = max(zeroRight, zero[i][1]);
    }
    return true;
}

bool able(int diff){
    int limSmall = totalMin + diff;
    int limBig = totalMax - diff;
    if(diff==13){
//        puts("");
    }
    for(int i=1; i<=n; i++){
        zero[i][0] = one[i][0] = 1e9;
        zero[i][1] = one[i][1] = 0;
        for(int j=1; j<=m; j++){
            if(limSmall < arr[i][j] && arr[i][j] < limBig) return false;
            if(arr[i][j] <= limSmall && arr[i][j] < limBig) zero[i][0] = min(zero[i][0],j), zero[i][1] = max(zero[i][1],j);
            if(arr[i][j] > limSmall && arr[i][j] >= limBig) one[i][0] = min(one[i][0],j), one[i][1] = max(one[i][1],j);
        }
    }

    if(solve()) return true;
    flipArr();
    if(solve()) return true;
    swapArr();
    if(solve()) return true;
    flipArr();
    if(solve()) return true;
    return false;
}

int main(){
    totalMin = 1e9, totalMax = 0;
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d", &arr[i][j]);
            totalMin = min(totalMin, arr[i][j]);
            totalMax = max(totalMax, arr[i][j]);
        }
    }

    int MIN = 0, MAX = 1e9, ANS = 1e9;
    while(MIN <= MAX){
        int MID = (MIN + MAX) / 2;
        if(able(MID)) ANS = MID, MAX = MID-1;
        else MIN = MID+1;
    }

    printf("%d", ANS);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf("%d", &arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40