Submission #480023

#	Time	Username	Problem	Language	Result	Execution time	Memory
480023		howboutsleep	Bajka (COCI20_bajka)	C++17	0 / 70	3 ms	588 KiB

bajka

#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 < cpos[s2[idx2]-'A'].size ()) {
      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);
  }

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

  cout << endl;

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

Compilation message (stderr)

bajka.cpp: In function 'void process(long long int, int, long long int)':
bajka.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if (cposi + i < cpos[s2[idx2]-'A'].size ()) {
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp: In function 'int main()':
bajka.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i < cpos[s2[0]-'A'].size (); i ++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 50