Submission #61181062

---

Source Code Expand

// I AM A MUSLIM

#include "bits/stdc++.h"

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

#define fast_io std::ios::sync_with_stdio(0);std::cin.tie(0)
#define lli long long int
#define flush fflush(stdout)
#define new_line printf("\n")
#define yn(a, b) printf("%s\n", (a) >= (b) ? "Yes":"No")
#define amodm(a, M) (((a)%M+M)%M)
// #define int lli

using pii = std::pair<int,int>;

const int MOD = 1000000007;
const int mxN = 500100;

// From YouKn0wWho's template
const int N = mxN;
const int MOD1 = 127657753, MOD2 = 987654319;
const int p1 = 137, p2 = 277;
int ip1, ip2;
std::pair<int, int> pw[N], ipw[N];

int power(long long n, long long k, const int mod) {
    int ans = 1 % mod;
    n %= mod;
    if (n < 0) n += mod;
    while (k) {
        if (k & 1) ans = (long long) ans * n % mod;
        n = (long long) n * n % mod;
        k >>= 1;
    }
    return ans;
}

void prec() {
    pw[0] =  {1, 1};
    for (int i = 1; i < N; i++) {
        pw[i].first = 1LL * pw[i - 1].first * p1 % MOD1;
        pw[i].second = 1LL * pw[i - 1].second * p2 % MOD2;
    }
    ip1 = power(p1, MOD1 - 2, MOD1);
    ip2 = power(p2, MOD2 - 2, MOD2);
    ipw[0] =  {1, 1};
    for (int i = 1; i < N; i++) {
        ipw[i].first = 1LL * ipw[i - 1].first * ip1 % MOD1;
        ipw[i].second = 1LL * ipw[i - 1].second * ip2 % MOD2;
    }
}

struct Hashing {
    int n;
    std::string s;  // 0 - indexed
    std::vector<std::pair<int, int>> hs;  // 1 - indexed
    Hashing() {}
    Hashing(std::string _s) {
        n = _s.size();
        s = _s;
        hs.emplace_back(0, 0);
        for (int i = 0; i < n; i++) {
            std::pair<int, int> p;
            p.first = (hs[i].first + 1LL * pw[i].first * s[i] % MOD1) % MOD1;
            p.second = (hs[i].second + 1LL * pw[i].second * s[i] % MOD2) % MOD2;
            hs.push_back(p);
        }
    }
    std::pair<int, int> get_hash(int l, int r) {  // 1 - indexed
        assert(1 <= l && l <= r && r <= n);
        std::pair<int, int> ans;
        ans.first = (hs[r].first - hs[l - 1].first + MOD1) * 1LL * ipw[l - 1].first % MOD1;
        ans.second = (hs[r].second - hs[l - 1].second + MOD2) * 1LL * ipw[l - 1].second % MOD2;
        return ans;
    }
    std::pair<int, int> get_hash() {
        return get_hash(1, n);
    }
};

std::vector<std::unordered_map<int,int>> dp(mxN);

signed main() {
    int testCases=1;
    // scanf("%d",&testCases);
    
    prec();
    
    for (int TC = 1; TC <= testCases; TC++) {
        int k; scanf("%d",&k);
        std::string s, t;
        std::cin >> s >> t;
        int m = (int)s.size(), n = (int)t.size();
        Hashing hs(s);
        Hashing ht(t);
        
        std::function<int(int,int,int)> fn1 = [&] (int i, int j, int L) {
            if (i == 0) return j;
            if (j == 0) return i;
            if (dp[i].find(j) != dp[i].end()) return dp[i][j];
            if (L == 10) {
                if (hs.get_hash(1, i) == ht.get_hash(1, j)) return 0;
                return 100;
            }
            
            if (s[i - 1] == t[j - 1])
                return dp[i][j] = fn1(i - 1, j - 1, L);
            return dp[i][j] = 1 + std::min({fn1(i, j - 1, L+1), // Insert
                           fn1(i - 1, j, L+1), // Remove
                           fn1(i - 1, j - 1, L+1) // Replace
                           });
        };
        
        std::function<int(int,int,int)> fn = [&] (int i, int j, int L) {
            if (i == 0) return j;
            if (j == 0) return i;
            if (L == 10) {
                return fn1(i, j, 0);
                // return 0;
            }
            
            if (s[i - 1] == t[j - 1])
                return fn(i - 1, j - 1, L);
            return 1 + std::min({fn(i, j - 1, L+1), // Insert
                           fn(i - 1, j, L+1), // Remove
                           fn(i - 1, j - 1, L+1) // Replace
                           });
        };
        
        int ans = fn(m, n, 0);
        yn((ans<=k),1);
        
    }
    
    return 0;
}

/*

*/

Submission Info

Compile Error

./Main.cpp:5:13: warning: unknown pragma ignored [-Wunknown-pragmas]
#pragma GCC optimize("O3,unroll-loops")
            ^
./Main.cpp:6:13: warning: unknown pragma ignored [-Wunknown-pragmas]
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
            ^
./Main.cpp:18:11: warning: unused variable 'MOD' [-Wunused-const-variable]
const int MOD = 1000000007;
          ^
3 warnings generated.

Judge Result