█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 4106

Problema 0xc9 - Substring más corta con mínimo K caracteres diferentes

  • Autor: pipelin1010
  • Fecha: 2021-05-14 16:32:57 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.005 s 9 KBi
#2
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.005 s 12 KBi
#3
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.006 s 5 KBi
#4
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.006 s 3 KBi
#5
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.002 s 2 KBi
#6
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.004 s 1 KBi
#7
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.005 s 8 KBi
#8
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.008 s 2 KBi
#9
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.004 s 1 KBi
#10
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.006 s 1 KBi
#11
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.008 s 8 KBi
#12
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.008 s 2 KBi
#13
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.01 s 2 KBi
#14
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.014 s 10 KBi
#15
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.009 s 9 KBi
#16
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.011 s 1 KBi
#17
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.012 s 6 KBi
#18
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.01 s 1 KBi
#19
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.005 s 3 KBi
#20
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.01 s 14 KBi
#21
Correcto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.006 s 2 KBi
#22
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.013 s 2 KBi
#23
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.006 s 2 KBi
#24
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.013 s 3 KBi
#25
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.007 s 2 KBi
#26
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.007 s 2 KBi
#27
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.011 s 1 KBi
#28
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.011 s 1 KBi
#29
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.009 s 2 KBi
#30
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.006 s 3 KBi
#31
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.007 s 2 KBi
#32
Incorrecto
                      main.cpp:106:27: warning: division by zero is undefined [-Wdivision-by-zero]
    if(ans < -1) ans = ans/0;
                          ^~
1 warning generated.

                    
0.005 s 2 KBi
Puntos totales: 66 / 100

Código

//
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MOD 1000000007
#define PI 3.14159265
#define EPS 1e-9
#define Pi acos(-1.0)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;

/*CODE START HERE*/

int visited[30];
int ans, k, aS, pivot, different;
string s;

int main(){
    ios::sync_with_stdio(0);
    clean(visited,0);
    cin >> s;
    cin >> k;

    ans = INF;
    aS = 0;
    pivot = 0;
    different = 0;

    forn(i,(int)s.size()){
        // cout << "NOW ON " << s[i] << " AS " << aS << " PIVOT " << pivot << " DIFFERENT " << different << "\n";

        if(visited[s[i]-'a']){
            // cout << "YA HA APARECIDO\n";
            for(int j = pivot; j < i; j++){
                aS--;
                visited[s[j]-'a']--;
                if(visited[s[j]-'a'] == 0){
                    pivot = j+1;
                    different--;
                    break;
                }
            }
        }

        visited[s[i]-'a']++;
        if(visited[s[i]-'a'] == 1){
            different++;
        }

        if(different > k){
            // cout << "IN\n";
            for(int j = pivot; j <= i; j++){
                aS--;
                visited[s[j]-'a']--;
                if(visited[s[j]-'a'] == 0){
                    different--;
                }

                if(different < k){
                    pivot = j;
                    different++;
                    visited[s[j]-'a']++;
                    aS++;
                    break;
                }

                
            }
        }

        aS++;
        // cout << "NOW ON " << s[i] << " AS " << aS << " PIVOT " << pivot << " DIFFERENT " << different << "\n";
        if(different==k)
            ans = min(ans,aS);

        char temp = s[i];
        while(true){
            i++;
            if(i >= (int)s.size()){
                break;
            }

            if(s[i] != temp){
                i--;
                break;
            }

            visited[s[i]-'a']++;

            aS++;
            if(different==k)
                ans = min(ans,aS);
        }
        // cout << "NOW ON " << s[i] << " AS " << aS << " PIVOT " << pivot << " DIFFERENT " << different << "\n";
    }
    if(ans == INF) ans = -1;
    if(ans < -1) ans = ans/0;
    cout << ans << "\n";
    return 0;
}