oj.uz

Submission #972073

# Submission time Handle Problem Language Result Execution time Memory
972073 2024-04-30T03:38:28 Z Whisper Lamps (JOI19_lamps) C++17
4 / 100
 108 ms 67128 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nArr;
string s, t;
const int MAX = 1e6 + 5;
int dp[MAX][2][3];

#define NOT 0
#define OFF 1
#define ON 2

int A[MAX], B[MAX];
void Whisper(){
    cin >> nArr >> s >> t;
    FOR(i, 1, nArr) A[i] = (s[i - 1] - '0');
    FOR(i, 1, nArr) B[i] = (t[i - 1] - '0');
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0] = 0;
    REP(i, nArr) REP(state, 2) REP(k, 3) REP(nxt_state, 2) REP(v, 3){
        int bit;
        if (v == NOT) bit = A[i + 1];
        else bit = v - 1;
        if(nxt_state) bit ^= 1;
        if(bit == B[i + 1])
            minimize(dp[i + 1][nxt_state][v], dp[i][state][k] + (k < v) + (state != nxt_state && nxt_state));
    }
    int ans = INF;
    REP(state, 2) REP(k, 3) minimize(ans, dp[nArr][state][k]);
    cout << ans;
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 50520 KB Output is correct
2 Correct 13 ms 50400 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50524 KB Output is correct
5 Correct 13 ms 50556 KB Output is correct
6 Correct 12 ms 50520 KB Output is correct
7 Correct 11 ms 50524 KB Output is correct
8 Correct 13 ms 50524 KB Output is correct
9 Correct 11 ms 50392 KB Output is correct
10 Correct 12 ms 50524 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Incorrect 11 ms 50540 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 50520 KB Output is correct
2 Correct 13 ms 50400 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50524 KB Output is correct
5 Correct 13 ms 50556 KB Output is correct
6 Correct 12 ms 50520 KB Output is correct
7 Correct 11 ms 50524 KB Output is correct
8 Correct 13 ms 50524 KB Output is correct
9 Correct 11 ms 50392 KB Output is correct
10 Correct 12 ms 50524 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Incorrect 11 ms 50540 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 50392 KB Output is correct
2 Correct 11 ms 50376 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50524 KB Output is correct
5 Correct 12 ms 50524 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 97 ms 67128 KB Output is correct
8 Correct 108 ms 67032 KB Output is correct
9 Correct 104 ms 67128 KB Output is correct
10 Correct 106 ms 66980 KB Output is correct
11 Correct 104 ms 66980 KB Output is correct
12 Correct 103 ms 66916 KB Output is correct
13 Correct 102 ms 66980 KB Output is correct
14 Correct 106 ms 67128 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 50520 KB Output is correct
2 Correct 13 ms 50400 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50524 KB Output is correct
5 Correct 13 ms 50556 KB Output is correct
6 Correct 12 ms 50520 KB Output is correct
7 Correct 11 ms 50524 KB Output is correct
8 Correct 13 ms 50524 KB Output is correct
9 Correct 11 ms 50392 KB Output is correct
10 Correct 12 ms 50524 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Incorrect 11 ms 50540 KB Output isn't correct
13 Halted 0 ms 0 KB -