Submission #851421

#TimeUsernameProblemLanguageResultExecution timeMemory
851421vjudge1Bajka (COCI20_bajka)C++17
70 / 70
24 ms600 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif #include <bits/stdc++.h> #define int long long #define pb push_back #define lim 1000000 #define till 1000001 // # of primes till 1e6 = 7e4 using namespace std; using pii = array<int,2>; const int mod=1000000007ll; unordered_map<char,vector<int>>all; void solve(){ int n,m; cin>>n>>m; string s1,s2; cin>>s1>>s2; for(int i=0;i<n;i++){ all[s1[i]].pb(i); } vector<pii>past; for(int i:all[s2[0]]){ past.pb({i,0}); } for(int i=1;i<m;i++){ /* for(int j=0;j<past.size();j++){ cerr<<past[j][0]<<" "<<past[j][1]<<"\n"; } cerr<<"\n"; */ vector<pii>now; //cerr<<"ok1\n"; for(int j:all[s2[i]]){ now.pb({j,INT_MAX}); } //cerr<<past.size()<<"\n"; //cerr<<"ok2\n"; for(int j=0;j<past.size();j++){ //cerr<<j<<"i\n"; for(int k=0;k<past.size();k++){ //cerr<<k<<"k\n"; if(j!=k){ past[k][1]=min(past[k][1],past[j][1]+abs(past[j][0]-past[k][0])); } //cerr<<k<<"K\n"; } //cerr<<j<<"j\n"; } //cerr<<"ok3\n"; for(int j=0;j<now.size();j++){ for(int k=0;k<past.size();k++){ if(abs(now[j][0]-past[k][0])==1){ //cerr<<j<<" "<<k<<"\n"; //cerr<<"sure "<<now[j][0]<<" "<<past[k][0]<<"\n"; now[j][1]=min(now[j][1],past[k][1]+1); }//else cerr<<"nope "<<now[j][0]<<" "<<past[k][0]<<"\n"; } } //cerr<<"ok4\n"; past.assign(now.begin(),now.end()); } int mini=INT_MAX; for(int i=0;i<past.size();i++){ mini=min(mini,past[i][1]); } if(mini==INT_MAX){ cout<<-1; }else{ cout<<mini; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #ifdef Local #ifndef INTERACTIVE freopen("in","r",stdin); freopen("out","w",stdout); #endif #endif int t=1; //cin>>t; while (t--) { solve(); } }

Compilation message (stderr)

bajka.cpp: In function 'void solve()':
bajka.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j=0;j<past.size();j++){
      |                     ~^~~~~~~~~~~~
bajka.cpp:44:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int k=0;k<past.size();k++){
      |                         ~^~~~~~~~~~~~
bajka.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0;j<now.size();j++){
      |                     ~^~~~~~~~~~~
bajka.cpp:55:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int k=0;k<past.size();k++){
      |                         ~^~~~~~~~~~~~
bajka.cpp:67:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<past.size();i++){
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...