ABC138-E. Strings of Impurity

작성일

https://atcoder.jp/contests/abc138/tasks/abc138_e

  • 의외로 빨리풀었다. 사실 D의 충격이 커서 E를 못풀줄알았다.
  • 걍 냅다 Binary Search 두번 하는 식으로 품..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

string s, t;
vector<int> pos[26];

int main() {
  ios::sync_with_stdio(false);
  cin >> s >> t;
  for(int i = 0; i < s.size(); i++)
    pos[s[i]-'a'].push_back(i);
  long long ans = 0, cur = 0;
  for(int i = 0; i < t.size(); i++) {
    auto& v = pos[t[i]-'a'];
    auto it = lower_bound(v.begin(), v.end(), cur);
    if (it != v.end()) {
      cur = *it+1;
      continue;
    }
    ans += s.size();
    cur = 0;
    it = lower_bound(v.begin(), v.end(), cur);
    if (it != v.end())
      cur = *it+1;
    else {
      cout << -1;
      return 0;
    }
  }
  cout << ans + cur;
}