Submission #915453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915453	2024-01-24T00:30:43 Z	vjudge1	Bajka (COCI20_bajka)	C++17	70 / 70	26 ms	600 KB

bajka

#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
#define inf 1e10
#define sz(v) (ll)v.size()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
#define fr(i, x) for(ll i=0 ; i<x ; i++)
#define fra(x, v) for(auto x:v)
#define fra1(x,v) for(auto &x:v)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define pb(x) push_back(x)
#define pll pair<ll, ll>
#define vll vector<ll>
#define mk(a, b) make_pair(a, b)
#define F first
#define S second

 
/*
 const long long maxN=0;
 que es eso??
 un maxN con 0
 que pront
 bueno muchachos a dormir
 */

const double PI=acos(-1), EPS=1e-9;
const ll MOD=1e9+7;


ll log2uwu(ll n){
    return 63-__builtin_clzll(n);
}

void solve(){
    ll n, m; cin>>n>>m;
    string a, b; cin>>a>>b;
    map<char, vll>posi;
    fr(i, n) posi[a[i]].pb(i);
    vector<pll>uwu;
    fra(x, posi[b[0]]) uwu.pb(mk(x, 0));
    fr(i, m){
        if(i==0) continue;
        vector<pll>unu;
        fra(x, posi[b[i]]) unu.pb(mk(x, inf));
        fr(j, uwu.size()){
            fr(k, uwu.size()){
                if(j==k) continue;
                uwu[k].S=min(uwu[k].S, uwu[j].S+abs(uwu[j].F-uwu[k].F));
            }
        }
        fr(j, unu.size()){
            fr(k, uwu.size()){
                if(abs(uwu[k].F-unu[j].F)==1){
                    unu[j].S=min(unu[j].S, uwu[k].S+1);
                }
            }
        }
        swap(uwu, unu);
    }
    ll cc=inf;
    fra(x, uwu) cc=min(cc, x.S);
    if(cc==inf) cout<<-1<<"\n";
    else cout<<cc<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
     solve();
    return 0;
}

Compilation message

bajka.cpp: In function 'void solve()':
bajka.cpp:22:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define fr(i, x) for(ll i=0 ; i<x ; i++)
......
   62 |         fr(j, uwu.size()){
      |            ~~~~~~~~~~~~~        
bajka.cpp:62:9: note: in expansion of macro 'fr'
   62 |         fr(j, uwu.size()){
      |         ^~
bajka.cpp:22:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define fr(i, x) for(ll i=0 ; i<x ; i++)
......
   63 |             fr(k, uwu.size()){
      |                ~~~~~~~~~~~~~    
bajka.cpp:63:13: note: in expansion of macro 'fr'
   63 |             fr(k, uwu.size()){
      |             ^~
bajka.cpp:22:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define fr(i, x) for(ll i=0 ; i<x ; i++)
......
   68 |         fr(j, unu.size()){
      |            ~~~~~~~~~~~~~        
bajka.cpp:68:9: note: in expansion of macro 'fr'
   68 |         fr(j, unu.size()){
      |         ^~
bajka.cpp:22:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define fr(i, x) for(ll i=0 ; i<x ; i++)
......
   69 |             fr(k, uwu.size()){
      |                ~~~~~~~~~~~~~    
bajka.cpp:69:13: note: in expansion of macro 'fr'
   69 |             fr(k, uwu.size()){
      |             ^~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	600 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	5 ms	476 KB	Output is correct
8	Correct	17 ms	348 KB	Output is correct
9	Correct	26 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	4 ms	344 KB	Output is correct