#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 ] + 1 ;
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[ 0 ][ 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 ] ;
nw[ j ][ i ] = n + 1 ;
if ( dp[ j ][ i ] < n ) { done = false ; }
}
}
if ( done == true ) {
cout << n - len << "\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
giraffes.cpp: In function 'void solve()':
giraffes.cpp:87:32: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | for ( auto [ ori , x ] : vr[ specx ][ enx ] ) {
| ^
giraffes.cpp:118:32: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
118 | for ( auto [ ori , x ] : hr[ specy ][ eny ] ) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
