oj.uz

Submission #1095695

# Submission time Handle Problem Language Result Execution time Memory
1095695 2024-10-03T02:11:54 Z Whisper Bajka (COCI20_bajka) C++17
20 / 70
 33 ms 71016 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, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 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());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

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 N, M;
string bad, fav;

#define MAX                 3003
int dp[MAX][MAX];

vector<int> on[26];

int nxt[MAX], prv[MAX];
void process(void){
    cin >> N >> M >> bad >> fav;
    bad = '@' + bad;
    fav = '@' + fav;
    queue<pair<int, int>> q;
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= N; ++i){
        int c = bad[i] - 'a';
        on[c].emplace_back(i);

        int len = (bad[i] == fav[1]);
        q.emplace(len, i);
        dp[len][i] = 0;
    }
    for (int i = 1; i <= N; ++i){
        int c = bad[i] - 'a';
        int pos = lower_bound(on[c].begin(), on[c].end(), i) - on[c].begin();
        nxt[i] = (pos + 1 < (int)on[c].size() ? on[c][pos + 1] : -1);
        prv[i] = (pos - 1 >= 0 ? on[c][pos - 1] : -1);
    }
    while(q.size()){
        int len, pos; tie(len, pos) = q.front(); q.pop();
        if(len == M) break;
        assert(dp[len][pos] != -1);
        int c = bad[pos] - 'a';

        if (nxt[pos] != -1){
            if(dp[len][nxt[pos]] == -1){
                dp[len][nxt[pos]] = dp[len][pos] + (nxt[pos] - pos);
                q.emplace(len, nxt[pos]);
            }
        }
        if (prv[pos] != -1){
            if(dp[len][prv[pos]] == -1){
                dp[len][prv[pos]] = dp[len][pos] + (pos - prv[pos]);
                q.emplace(len, prv[pos]);
            }
        }
        if(pos > 1){
            int nxt_len = len + (bad[pos - 1] == fav[len + 1]);

            if(nxt_len > len && dp[nxt_len][pos - 1] == -1){
                dp[nxt_len][pos - 1] = dp[len][pos] + 1;
                q.emplace(nxt_len, pos - 1);
            }
        }
        if(pos < N){
            int nxt_len = len + (bad[pos + 1] == fav[len + 1]);
            if(nxt_len > len && dp[nxt_len][pos + 1] == -1){
                dp[nxt_len][pos + 1] = dp[len][pos] + 1;
                q.emplace(nxt_len, pos + 1);
            }
        }
    }
    int ans = LINF;
    for (int i = 1; i <= N; ++i) if(dp[M][i] != -1){
        minimize(ans, dp[M][i]);
    }
    cout << (ans >= LINF ? -1 : ans);
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Compilation message

bajka.cpp: In function 'void process()':
bajka.cpp:71:13: warning: unused variable 'c' [-Wunused-variable]
   71 |         int c = bad[pos] - 'a';
      |             ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70976 KB Output is correct
2 Correct 31 ms 71004 KB Output is correct
3 Correct 31 ms 71004 KB Output is correct
4 Correct 31 ms 70996 KB Output is correct
5 Correct 31 ms 71016 KB Output is correct
6 Correct 33 ms 70876 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70996 KB Output is correct
2 Incorrect 32 ms 71016 KB Output isn't correct
3 Halted 0 ms 0 KB -