Submission #42091

#	Time	Username	Problem	Language	Result	Execution time	Memory
42091		chonka	The Kingdom of JOIOI (JOI17_joioi)	C++98	100 / 100	1435 ms	262144 KiB

joioi

#include<iostream>
#include<stdio.h>
using namespace std ;

#define MAXN 2007
int n , m ;
int a[ MAXN ][ MAXN ] ;

int mxval ;
int mnval ;
int ans ;

int st[ MAXN ] ;
int en[ MAXN ] ;

bool f ( int x ) {
    int i , j ;
    for ( i = 1 ; i <= n ; i ++ ) {
        st[ i ] = 0 ;
        for ( j = 1 ; j <= m ; j ++ ) {
            if ( a[ i ][ j ] < mxval - x ) { break ; }
            st[ i ] = j ;
        }
        en[ i ] = m + 1 ;
        for ( j = m ; j >= 1 ; j -- ) {
            if ( a[ i ][ j ] > mnval + x ) { break ; }
            en[ i ] = j ;
        }
    }
    for ( i = n - 1 ; i >= 1 ; i -- ) {
        st[ i ] = min ( st[ i ] , st[ i + 1 ] ) ;
    }
    for ( i = 2 ; i <= n ; i ++ ) {
        en[ i ] = max ( en[ i - 1 ] , en[ i ] ) ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        if ( st[ i ] < en[ i ] - 1 ) { return false ; }
    }
    return true ;
}

int getans ( ) {
    int l , r , mid ;
    l = 0 ;
    r = mxval - mnval ;
    while ( r - l > 3 ) {
        mid = ( l + r ) / 2 ;
        if ( f ( mid ) == true ) { r = mid ; }
        else { l = mid ; }
    }
    while ( f ( l ) == false ) { l ++ ; }
    return l ;
}


void flip_rows ( ) {
    int i , j ;
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= ( m / 2 ) ; j ++ ) {
            swap ( a[ i ][ j ] , a[ i ][ m - j + 1 ] ) ;
        }
    }
}
void flip_cols ( ) {
    int i , j ;
    for ( j = 1 ; j <= m ; j ++ ) {
        for ( i = 1 ; i <= ( n / 2 ) ; i ++ ) {
            swap ( a[ i ][ j ] , a[ n - i + 1 ][ j ] ) ;
        }
    }
}

void input ( ) {
    scanf ( "%d%d" , &n , &m ) ;
    int i , j ;
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= m ; j ++ ) {
            scanf ( "%d" , &a[ i ][ j ] ) ;
            if ( i == 1 && j == 1 ) {
                mnval = mxval = a[ i ][ j ] ;
            }
            if ( mxval < a[ i ][ j ] ) {
                mxval = a[ i ][ j ] ;
            }
            if ( mnval > a[ i ][ j ] ) {
                mnval = a[ i ][ j ] ;
            }
        }
    }
}

void solve ( ) {
    ans = mxval - mnval ;
    ans = min ( ans , getans ( ) ) ;
    flip_rows ( ) ;
    ans = min ( ans , getans ( ) ) ;
    flip_cols ( ) ;
    ans = min ( ans , getans ( ) ) ;
    flip_rows ( ) ;
    ans = min ( ans , getans ( ) ) ;
    printf ( "%d\n" , ans ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

joioi.cpp: In function 'void input()':
joioi.cpp:74:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &m ) ;
                                ^
joioi.cpp:78:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d" , &a[ i ][ j ] ) ;
                                           ^

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