oj.uz

답안 #915453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915453 2024-01-24T00:30:43 Z vjudge1 Bajka (COCI20_bajka) C++17
70 / 70
 26 ms 600 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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