Submission #6997589


Source Code Expand

Copy
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T1, class T2>bool chmax(T1& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<class T1, class T2>bool chmin(T1& a, const T2& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

string S, T;
vector<int> Schar_cnt(26);
vv<int> next_cindex;

int main() {
    cin >> S >> T;

    rep(i, S.size()) {
        Schar_cnt[S[i] - 'a']++;
    }

    bool ok = true;
    rep(i, T.size()) {
        if (Schar_cnt[T[i] - 'a'] == 0) {
            ok = false;
        }
    }

    if (!ok) {
        write(-1);
        return 0;
    }

    next_cindex = vvec(S.size(), 26, -1);
    vector<int> ci(26, -1);
    for (int i = S.size() - 1; i >= 0; --i) {
        ci[S[i] - 'a'] = i;

        for (int c = 0; c < 26; ++c) {
            next_cindex[i][c] = ci[c];
        }
    }

    ll ans = 0;
    int cur = 0;
    for (int i = 0; i < T.size(); ++i) {
        if (next_cindex[cur][T[i] - 'a'] >= 0) {
            ans += next_cindex[cur][T[i] - 'a'] - cur + 1;
            cur = next_cindex[cur][T[i] - 'a'] + 1;
        }
        else {
            ans += S.size() - cur;
            cur = 0;
            ans += next_cindex[cur][T[i] - 'a'] - cur + 1;
            cur = next_cindex[cur][T[i] - 'a'] + 1;
        }

        if (cur == S.size()) {
            cur = 0;
        }
    }

    write(ans);
}

Submission Info

Submission Time
Task E - Strings of Impurity
User myun
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2043 Byte
Status CE

Compile Error

./Main.cpp:9:72: error: ‘vector’ does not name a type
 using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
                                                                        ^
./Main.cpp: In function ‘auto vvec(int, int, T)’:
./Main.cpp:10:56: error: ‘vv’ was not declared in this scope
 template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
                                                        ^
./Main.cpp:10:60: error: expected primary-expression before ‘>’ token
 template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
                                                            ^
./Main.cpp:10:65: error: ‘vector’ was not declared in this scope
 template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
                                                                 ^
./Main.cpp:10:73: error: expected primary-expression before ‘>’ token
 template<class T>auto vvec(int n, int m, T...