Submission #870067

#	Time	Username	Problem	Language	Result	Execution time	Memory
870067		chonka	Giraffes (JOI22_giraffes)	C++98	100 / 100	5816 ms	5272 KiB

giraffes

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int MAXN = 8007 ;

int n ;
int a[ MAXN ] ;

int dp[ 4 ][ MAXN ] ;
int nw[ 4 ][ MAXN ] ;

vector < pii > hr[ 2 ][ MAXN ] ;
vector < pii > vr[ 2 ][ MAXN ] ;

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    for ( int j = 0 ; j < 4 ; ++ j ) {
        for ( int i = 1 ; i <= n ; ++ i ) {
            dp[ j ][ i ] = 0 ;
        }
    }
    for ( int len = 2 ; len <= n + 1 ; ++ len ) {
        for ( int j = 0 ; j < 4 ; ++ j ) {
            for ( int i = 1 ; i <= n ; ++ i ) {
                if ( dp[ j ][ i ] > n ) { continue ; }
                if ( ( j % 2 ) == 0 ) {
                    hr[ 0 ][ a[ i ] ].push_back ( { j , i } ) ;
                    hr[ 1 ][ a[ i ] + dp[ j ][ i ] ].push_back ( { j , i } ) ;
                }
                else {
                    hr[ 1 ][ a[ i ] ].push_back ( { j , i } ) ;
                    hr[ 0 ][ a[ i ] - dp[ j ][ i ] ].push_back ( { j , i } ) ;
                }
                if ( ( j / 2 ) == 0 ) {
                    vr[ 0 ][ i ].push_back ( { j , i } ) ;
                    vr[ 1 ][ i + dp[ j ][ i ] ].push_back ( { j , i } ) ;
                }
                else {
                    vr[ 1 ][ i ].push_back ( { j , i } ) ;
                    vr[ 0 ][ i - dp[ j ][ i ] ].push_back ( { j , i } ) ;
                }
            }
        }
        for ( int j = 0 ; j < 4 ; ++ j ) { 
            for ( int i = 1 ; i <= n ; ++ i ) {
                if ( dp[ j ][ i ] > n ) {
                    nw[ j ][ i ] = n + 1 ;
                    continue ;
                }
                nw[ j ][ i ] = dp[ j ][ i ] ;
                
                while ( nw[ j ][ i ] <= n ) {
                    int enx = i , eny = a[ i ] ;
                    int specx , specy ;
                    if ( ( j / 2 ) == 0 ) { enx += nw[ j ][ i ] ; specx = 1 ; }
                    else { enx -= nw[ j ][ i ] ; specx = 0 ; }

                    if ( ( j % 2 ) == 0 ) { eny += nw[ j ][ i ] ; specy = 1 ; }
                    else { eny -= nw[ j ][ i ] ; specy = 0 ; }
                    if ( enx < 1 || n < enx ) {
                        nw[ j ][ i ] = n + 1 ;
                        break ;
                    }
                    if ( eny < 1 || n < eny ) {
                        nw[ j ][ i ] = n + 1 ;
                        break ;
                    }
                    bool done = false ;
                    for ( auto [ ori , x ] : vr[ specx ][ enx ] ) {
                        if ( dp[ ori ][ x ] >= nw[ j ][ i ] ) { continue ; }
                        if ( ( ori % 2 ) == 0 ) {
                            if ( ( j % 2 ) == 0 ) {
                                if ( a[ i ] < a[ x ] && a[ x ] + dp[ ori ][ x ] <= eny ) {
                                    done = true ;
                                    break ;
                                }
                            }
                            else {
                                if ( eny <= a[ x ] && a[ x ] + dp[ ori ][ x ] < a[ i ] ) {
                                    done = true ;
                                    break ;
                                }
                            }
                        }
                        else {
                            if ( ( j % 2 ) == 0 ) {
                                if ( a[ i ] < a[ x ] - dp[ ori ][ x ] && a[ x ] <= eny ) {
                                    done = true ;
                                    break ;
                                }
                            }
                            else {
                                if ( eny <= a[ x ] - dp[ ori ][ x ] && a[ x ] < a[ i ] ) {
                                    done = true ;
                                    break ;
                                }
                            }
                        }
                    }
                    for ( auto [ ori , x ] : hr[ specy ][ eny ] ) {
                        if ( dp[ ori ][ x ] >= nw[ j ][ i ] ) { continue ; }

                        if ( ( ori / 2 ) == 0 ) {
                            if ( ( j / 2 ) == 0 ) {
                                if ( i < x && x + dp[ ori ][ x ] <= enx ) {
                                    done = true ;
                                    break ;
                                }
                            }
                            else {
                                if ( enx <= x && x + dp[ ori ][ x ] < i ) {
                                    done = true ;
                                    break ;
                                }
                            }
                        }
                        else {
                            if ( ( j / 2 ) == 0 ) {
                                if ( i < x - dp[ ori ][ x ] && x <= enx ) {
                                    done = true ;
                                    break ;
                                }
                            }
                            else {
                                if ( enx <= x - dp[ ori ][ x ] && x < i ) {
                                    done = true ;
                                    break ;
                                }
                            }
                        }
                    }
                    if ( done == true ) { break ; }
                    ++ nw[ j ][ i ] ;
                }
            }
        }
        for ( int i = 1 ; i <= n ; ++ i ) {
            hr[ 0 ][ i ].clear ( ) , hr[ 1 ][ i ].clear ( ) ;
            vr[ 0 ][ i ].clear ( ) , vr[ 1 ][ i ].clear ( ) ;
        }
        bool done = true ;
        for ( int j = 0 ; j < 4 ; ++ j ) {
            for ( int i = 1 ; i <= n ; ++ i ) {
                dp[ j ][ i ] = nw[ j ][ i ] ;
                if ( dp[ j ][ i ] < n ) { done = false ; }
            }
        }
        if ( done == true ) {
            cout << n - ( len - 1 ) << "\n" ;
            return ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

Compilation message (stderr)

giraffes.cpp: In function 'void solve()':
giraffes.cpp:86:32: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |                     for ( auto [ ori , x ] : vr[ specx ][ enx ] ) {
      |                                ^
giraffes.cpp:117:32: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |                     for ( auto [ ori , x ] : hr[ specy ][ eny ] ) {
      |                                ^

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41