Submission #2528138


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N=5000;
char s[N+5];
int n,v[N+5],k;

int sol[N+5],mom[N+5];
bool viz[7][N+5];

bool sch()
{
    int mi=min(sol[0],mom[0]);
    for(int i=1;i<=mi;i++)
    {
        if(sol[i]<mom[i])
            return 0;
        if(mom[i]<sol[i])
            return 1;
    }
    if(mom[0]<sol[0])
        return 1;
    return 0;

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin.getline(s,N+5);
    n=strlen(s);
    for(int i=0;i<n;i++)
        v[i+1]=s[i];
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        sol[0]=n;
        for(int j=1;j<=sol[0];j++)
            sol[j]=(1<<30);
        for(int l=1;l<=5;l++)
        {
            for(int st=1;st+l-1<=n;st++)
            {///continue;
                if(viz[l][st]==1)continue;
                int dr=st+l-1;
                mom[0]=0;
                for(int j=st;j<=dr;j++)
                    mom[++mom[0]]=v[j];
                if(sch()==1)
                {
                    sol[0]=mom[0];
                    for(int i=1;i<=sol[0];i++)
                        sol[i]=mom[i];
                }
            }
        }
        for(int st=1;st+sol[0]-1<=n;st++)
        {
            int dr=st+sol[0]-1;
            bool ok=1;
            int y=1;
            for(int j=st;j<=dr;j++)
            {
                if(v[j]!=sol[y])
                {
                    ok=0;
                    break;
                }
                y++;
            }
            if(ok==1)
                viz[sol[0]][st]=1;
        }
    }
    for(int i=1;i<=sol[0];i++)
        cout<<char(sol[i]);
    cout<<"\n";
    return 0;
}
/**
**/

Submission Info

Submission Time
Task C - K-th Substring
User master_mihnea
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1735 Byte
Status AC
Exec Time 2 ms
Memory 384 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 200 / 200 100 / 100
Status
AC × 3
AC × 11
AC × 19
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
Subtask 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 2_011.txt, 2_012.txt, 2_013.txt, 2_014.txt, 2_015.txt, 2_016.txt, 2_017.txt, 2_018.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
2_011.txt AC 2 ms 384 KB
2_012.txt AC 2 ms 384 KB
2_013.txt AC 2 ms 384 KB
2_014.txt AC 2 ms 384 KB
2_015.txt AC 2 ms 384 KB
2_016.txt AC 2 ms 384 KB
2_017.txt AC 2 ms 384 KB
2_018.txt AC 2 ms 384 KB