Submission #7064940


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

set<ll> can[300];
ll ans[100100];

signed main() {
  string s, t;
  cin >> s >> t;
  ll ns = s.size(), nt = t.size();
  rep(i, ns) {
    can[s[i]].insert(i);
  }
  rep(i, 300) {
    if (can[i].size() == 0)
      continue;
    auto mi = *can[i].begin();
    can[i].insert(mi + ns);
    //printf("%c :", i);
    //for (auto c : can[i]) {
    //  printf("%d ", c);
    //}
    //printf("\n");
  }

  // printf("ans: ");
  ll pos = -1;
  rep(i, nt) {
    if (can[t[i]].size() == 0) {
      cout << -1 << endl;
      return 0;
    }
    ll now = pos % ns;
    ll nxt = *can[t[i]].lower_bound((pos+1) % ns);
    if (nxt > now) {
      pos = pos + (nxt-now);
    } else {
      pos = pos + (ns+nxt-now);
    }
    ans[i] = pos;
    //printf("%d ", ans[i]);
  }
  //printf("\n");
  cout << ans[nt-1] + 1 << endl;
  return 0;
}

Submission Info

Submission Time
Task E - Strings of Impurity
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1094 Byte
Status
Exec Time 43 ms
Memory 5888 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 500 / 500 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1 ms 256 KB
b09 1 ms 256 KB
b10 43 ms 5888 KB
b11 32 ms 5888 KB
b12 34 ms 5888 KB
b13 34 ms 5888 KB
b14 43 ms 5888 KB
b15 43 ms 5888 KB
b16 43 ms 5888 KB
b17 40 ms 5888 KB
b18 40 ms 5888 KB
b19 39 ms 5888 KB
b20 27 ms 5888 KB
b21 29 ms 5888 KB
b22 28 ms 5888 KB
b23 28 ms 5888 KB
b24 28 ms 5888 KB
b25 38 ms 5888 KB
b26 35 ms 5888 KB
b27 33 ms 5888 KB
b28 30 ms 5888 KB
b29 28 ms 5888 KB
b30 27 ms 5888 KB
b31 23 ms 5120 KB
b32 7 ms 1280 KB
b33 6 ms 896 KB
b34 28 ms 5120 KB
b35 22 ms 4992 KB
b36 30 ms 5888 KB
b37 30 ms 5888 KB
b38 31 ms 5888 KB
b39 31 ms 5888 KB
b40 26 ms 5888 KB
b41 25 ms 5888 KB
b42 31 ms 5120 KB
b43 25 ms 5120 KB
b44 34 ms 5888 KB
b45 34 ms 5888 KB