oj.uz

Submission #480024

# Submission time Handle Problem Language Result Execution time Memory
480024 2021-10-14T11:05:49 Z howboutsleep Bajka (COCI20_bajka) C++17
0 / 70
 4 ms 588 KB 
#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define NUM 301
#define inf 1e9
#define MOD 1000000007

using namespace std;

bool pos;
vector <int> cpos[26];
int n, m;
ll res = inf;
string s1, s2;

void process (ll cposi, int idx2, ll cnt) {
  if (cnt > res) return;
  //cout << idx2 <<':'<< cpos[s2[idx2]-'A'][cposi] << endl;
  if (idx2 == m - 1) {
    //cout << cnt << endl << endl;
    res = min(res, cnt);
    return;
  }
  if (cpos[s2[idx2]-'A'][cposi] > 0) {
    if(s1[cpos[s2[idx2]-'A'][cposi] - 1] == s2[idx2 + 1]) {
      //cout << '+';
      process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi] - 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + 1);
    }
  }
  if (cpos[s2[idx2]-'A'][cposi] < n - 1) {
    if(s1[cpos[s2[idx2]-'A'][cposi] + 1] == s2[idx2 + 1]) {
      process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi] + 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + 1);
    }
  }

  int sz = cpos[s2[idx2]-'A'].size ();

  for (int i = 1; i < max(cposi + 1, sz - cposi); i ++) {
    if (cposi - i >= 0) {
      if (cpos[s2[idx2]-'A'][cposi - i] > 0) {
        if(s1[cpos[s2[idx2]-'A'][cposi - i] - 1] == s2[idx2 + 1]) {
          //cout << '-';
          process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi - i] - 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi - i] - cpos[s2[idx2]-'A'][cposi]) + 1);
        }
      }
      if (cpos[s2[idx2]-'A'][cposi - i] < n - 1) {
        if(s1[cpos[s2[idx2]-'A'][cposi - i] + 1] == s2[idx2 + 1]) {
          //cout << '-';
          process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi - i] + 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi - i] - cpos[s2[idx2]-'A'][cposi]) + 1);
        }
      }  
    }

    if (cposi + i < sz) {
      if (cpos[s2[idx2]-'A'][cposi + i] > 0) {
        if(s1[cpos[s2[idx2]-'A'][cposi + i] - 1] == s2[idx2 + 1]) {
          //cout << '-';
          process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi + i] - 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi + i] - cpos[s2[idx2]-'A'][cposi]) + 1);
        }
      }
      if (cpos[s2[idx2]-'A'][cposi + i] < n - 1) {
        if(s1[cpos[s2[idx2]-'A'][cposi + i] + 1] == s2[idx2 + 1]) {
          //cout << '-';
          process(find(cpos[s2[idx2 + 1]-'A'].begin(), cpos[s2[idx2 + 1]-'A'].end(), cpos[s2[idx2]-'A'][cposi + i] + 1)-cpos[s2[idx2 + 1]-'A'].begin(), idx2 + 1, cnt + abs(cpos[s2[idx2]-'A'][cposi + i] - cpos[s2[idx2]-'A'][cposi]) + 1);
        }
      }  
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  
  cin >> s1 >> s2;

  for (int i = 0; i < n; i ++) {
    cpos [s1[i]-'A'].push_back(i);
  }

  int sz = cpos[s2[0]-'A'].size ();
  for (int i = 0; i < sz; i ++) {
    process (i, 0, 0);
  }

  cout << endl;

  if (res != inf) {
    cout << res;
  }
  else {
    cout << -1;
  }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -