Submission #236422

#	Time	Username	Problem	Language	Result	Execution time	Memory
236422		Dilshod_Imomov	Lamps (JOI19_lamps)	C++17	0 / 100	1104 ms	106184 KiB

lamp

# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # pragma GCC optimize "-O3"
# define int long long
using namespace std;

const int N = 1e6 + 7;
const int INF = 1e9 + 7;

int dp[N], DP[N][4], dp0[N][4], dp3[N][4];
string s, t;

int Min( int i, int j ) {
	int mn = dp0[i - 1][j], mn2 = INF, x = (j != 3);
	for ( int k = 0; k < 4; k++ ) {
		if ( k != j ) {
			mn2 = min( mn2, dp0[i - 1][k] + x );
		}
	}
	return min( mn, mn2 );
}
int Min1( int i, int j ) {
    int mn = dp3[i - 1][j], mn2 = INF, x = (j != 3);
    for ( int k = 0; k < 4; k++ ) {
        if ( k != j ) {
            mn2 = min( mn2, dp3[i - 1][k] + x );
        }
    }
    return min( mn, mn2 );
}

void output( int i ) { 
	cout << dp0[i][0] << "            " << dp0[i][1] << "            " << dp0[i][2] << "            " << dp0[i][3] << '\n';
}

void calc0( char x, int i ) {
    if ( x == '1' ) {
        if ( t[i] == '1' ) {
            dp0[i][1] = Min( i, 1 );
            dp0[i][3] = Min( i, 3 );
            dp0[i][0] = INF;
            dp0[i][2] = INF;
        }
        else {
            dp0[i][0] = Min( i, 0 );
            dp0[i][2] = Min( i, 2 );
            dp0[i][1] = INF;
            dp0[i][3] = INF;
        }
    }
    else {
        if ( t[i] == '1' ) {
            dp0[i][1] = Min( i, 1 );
            dp0[i][2] = Min( i, 2 );
            dp0[i][0] = INF;
            dp0[i][3] = INF;
        }
        else {
            dp0[i][0] = Min( i, 0 );
            dp0[i][3] = Min( i, 3 );
            dp0[i][1] = INF;
            dp0[i][2] = INF;
        }
    }
}
void calc1( char x, int i ) {
    if ( x == '1' ) {
        if ( t[i] == '1' ) {
            dp3[i][1] = Min1( i, 1 );
            dp3[i][3] = Min1( i, 3 );
            dp3[i][0] = INF;
            dp3[i][2] = INF;
        }
        else {
            dp3[i][0] = Min1( i, 0 );
            dp3[i][2] = Min1( i, 2 );
            dp3[i][1] = INF;
            dp3[i][3] = INF;
        }
    }
    else {
        if ( t[i] == '1' ) {
            dp3[i][1] = Min1( i, 1 );
            dp3[i][2] = Min1( i, 2 );
            dp3[i][0] = INF;
            dp3[i][3] = INF;
        }
        else {
            dp3[i][0] = Min1( i, 0 );
            dp3[i][3] = Min1( i, 3 );
            dp3[i][1] = INF;
            dp3[i][2] = INF;
        }
    }
}

int32_t main() {
    speed;
    int n;
    cin >> n;
    cin >> s >> t;
    if ( s[0] == '1' ) {
    	if ( t[0] == '0' ) {
    		dp0[0][0] = 1;
    		dp0[0][2] = 1;
            dp0[0][1] = INF;
            dp0[0][3] = INF;
    	}
    	if ( t[0] == '1' ) {
    		dp0[0][1] = 1;
    		dp0[0][3] = 0;
            dp0[0][0] = INF;
            dp0[0][2] = INF;
    	}
    }
    else {
    	if ( t[0] == '0' ) {
    		dp0[0][0] = 1;
    		dp0[0][3] = 0;
            dp0[0][2] = INF;
            dp0[0][1] = INF;
    	}
    	if ( t[0] == '1' ) {
    		dp0[0][1] = 1;
    		dp0[0][2] = 1;
            dp0[0][0] = INF;
            dp0[0][3] = INF;
    	}
    }
    // change( 0 );
    DP[0][0] = min( { dp0[0][0], dp0[0][1], dp0[0][2], dp0[0][3] } );
    if ( s[0] == '0' ) {
        if ( t[0] == '0' ) {
            dp3[0][0] = 1;
            dp3[0][2] = 1;
            dp3[0][1] = INF;
            dp3[0][3] = INF;
        }
        if ( t[0] == '1' ) {
            dp3[0][1] = 1;
            dp3[0][3] = 0;
            dp3[0][0] = INF;
            dp3[0][2] = INF;
        }
    }
    else {
        if ( t[0] == '0' ) {
            dp3[0][0] = 1;
            dp3[0][3] = 0;
            dp3[0][1] = INF;
            dp3[0][2] = INF;
        }
        if ( t[0] == '1' ) {
            dp3[0][1] = 1;
            dp3[0][2] = 1;
            dp3[0][0] = INF;
            dp3[0][3] = INF;
        }
    }
    // change1( 0 );
    DP[0][3] = min( { dp3[0][0], dp3[0][1], dp3[0][2], dp3[0][3] } );
    // output(0);
    for ( int i = 1; i < n; i++ ) {
        calc0( s[i], i );
        DP[i][0] = min( { dp0[i][0], dp0[i][1], dp0[i][2], dp0[i][3] } );
        char x = '0' + ( 1 - (s[i] - '0') );
        calc1( x, i );
        DP[i][3] = min( { dp3[i][0], dp3[i][1], dp3[i][2], dp3[i][3] } );
    	// output(i);
    }
    int one = 0, zero = 0, cnt0 = 0, cnt1 = 0;
    for ( int i = 0; i < n; i++ ) {
        dp[i] = INF;
        if ( t[i] == '0' ) {
            if ( !zero ) {
                zero = 1;
                cnt0++;
            }
            one = 0;
        }
        else {
            if ( !one ) {
                one = 1;
                cnt1++;
            }
            zero = 0;
        }
        DP[i][1] = cnt0;
        DP[i][2] = cnt1;
        // cout << i << " " << DP[i][0] << ' ' << DP[i][1] << ' ' << DP[i][2] << " " << DP[i][3] << "\n";
    }
    for ( int i = 0; i < n; i++ ) {
        for ( int j = i; j >= 0; j-- ) {
            int cnt = 0;
            if ( j ) {
                cnt += dp[j - 1];
                for ( int k = 1; k < 4; k++ ) {
                    dp[i] = min( dp[i], DP[i][k] - DP[j - 1][k] + cnt + 1 );
                }
            }
        }
        dp[i] = min( { dp[i], DP[i][0], DP[i][1] + 1, DP[i][2] + 1, DP[i][3] + 1 } );
        // cout << i << " " << dp[i] << "\n";
    }
    cout << dp[n - 1];
}
// 1. DP[i][0] = minimum number of moves without wrong range queries from 1->i : dp0; Done
// 2. DP[i][1] = number of 1 segments ; Done
// 3. DP[i][2] = number of 0 segments ; Done
// 4. DP[i][3] = same as [0] but with 1 - s[i] : dp3; Done
// 5. dp[i] = minimum number of moves to solve till i
// 6. change dp[i] with minimum dp[j - 1] - DP[j - 1][k]; j < i, k < 4
// 7. store the 6'th point in a set to find the minimum
// 8. return dp[n - 1];
// 9. 0% belief in this code

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49