CSES - E4590 2018 2 - Results
Submission details
Task:Edit distance
Sender:henrikaalto
Submission time:2018-09-22 15:43:39 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1UNKNOWN--details
#2UNKNOWN--details
#3UNKNOWN--details
#4UNKNOWN--details
#5UNKNOWN--details
#6UNKNOWN--details
#7UNKNOWN--details
#8UNKNOWN--details
#9UNKNOWN--details
#10UNKNOWN--details
#11UNKNOWN--details
#12UNKNOWN--details
#13UNKNOWN--details
#14UNKNOWN--details
#15UNKNOWN--details
#16UNKNOWN--details
#17UNKNOWN--details
#18UNKNOWN--details
#19UNKNOWN--details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(size_t i=0;i<=n;i++){d[i][0]=i;}
                    ~^~~
input/code.cpp:29:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(size_t i=0;i<=m;i++){d[0][i]=i;}
                    ~^~~
input/code.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(size_t i=1;i<=n;i++){
                    ~^~~
input/code.cpp:31:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(size_t j=1;j<=m;j++){
                        ~^~~

Code

#include<iostream>
#include<string>

std::string x,y;
long long n,m;
int d[5101][5101];

int cost(int a,int b){
    if(x[a]==y[b]){return 0;}
    return 1;
}

int distance(int a,int b){
    
    int ans0= d[a][b-1]+1;
    int ans1= d[a-1][b]+1;
    int ans2= d[a-1][b-1]+cost(a-1,b-1);
    return std::min(ans0,std::min(ans1,ans2));
}



int main() {
    std::cin.tie(NULL);std::ios_base::sync_with_stdio(0);
    std::cin>>x>>y;
    n=x.length();
    m=y.length();
    for(size_t i=0;i<=n;i++){d[i][0]=i;}
    for(size_t i=0;i<=m;i++){d[0][i]=i;}
    for(size_t i=1;i<=n;i++){
        for(size_t j=1;j<=m;j++){
            d[i][j]=distance(i,j);
        }
    }
    //for(size_t i=0;i<=m;i++){
    //    for(size_t j=0;j<=n;j++){
    //        std::cout<<d[j][i]<<" ";
    //   }   
    //    std::cout<<std::endl;
    //}
    std::cout<<d[n][m]<<std::endl;
    //std::cout<<cost(1,1);
}

Test details

Test 1

Verdict: UNKNOWN

input
NEABJPJOI
RFMQRJKJKIA

correct output
8

user output
(not available)

Test 2

Verdict: UNKNOWN

input
TWXFUABGBNLTBFNSUVQW
GPNJILFXJUIZPLTVUIB

correct output
19

user output
(not available)

Test 3

Verdict: UNKNOWN

input
HSMOWJXKGRWSMD
JMRTLLNPXKKXZC

correct output
14

user output
(not available)

Test 4

Verdict: UNKNOWN

input
NGPYCNPO
UQPXWVLGHC

correct output
9

user output
(not available)

Test 5

Verdict: UNKNOWN

input
SQTCKWAMFJEBV
IUWGGNJOMQFP

correct output
13

user output
(not available)

Test 6

Verdict: UNKNOWN

input
VDREWLLHMEVGFGBXJJOSSLHNJBOTRK...

correct output
4047

user output
(not available)

Test 7

Verdict: UNKNOWN

input
EIIUUQXSAFMTRSEZSFYNSAGHUWTSGY...

correct output
3769

user output
(not available)

Test 8

Verdict: UNKNOWN

input
HVOXUVAZYFBKEWQXVGJMYXCCXBWRNW...

correct output
3806

user output
(not available)

Test 9

Verdict: UNKNOWN

input
AWGASQANDZQTVKXQDKWNADQDBXKCOK...

correct output
4069

user output
(not available)

Test 10

Verdict: UNKNOWN

input
WXAAJJALZRLGLSXDPUPURULYINBFGX...

correct output
3874

user output
(not available)

Test 11

Verdict: UNKNOWN

input
A
A

correct output
0

user output
(not available)

Test 12

Verdict: UNKNOWN

input
A
B

correct output
1

user output
(not available)

Test 13

Verdict: UNKNOWN

input
AA
A

correct output
1

user output
(not available)

Test 14

Verdict: UNKNOWN

input
A
AA

correct output
1

user output
(not available)

Test 15

Verdict: UNKNOWN

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
5000

user output
(not available)

Test 16

Verdict: UNKNOWN

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
0

user output
(not available)

Test 17

Verdict: UNKNOWN

input
B
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
5000

user output
(not available)

Test 18

Verdict: UNKNOWN

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
5000

user output
(not available)

Test 19

Verdict: UNKNOWN

input
KITTEN
SITTING

correct output
3

user output
(not available)