QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107323#850. Edit Distance Yet AgainSortingWA 14032ms84116kbC++205.7kb2023-05-20 23:13:012023-05-20 23:13:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 23:13:03]
  • 评测
  • 测评结果:WA
  • 用时:14032ms
  • 内存:84116kb
  • [2023-05-20 23:13:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 1e6 + 7 ;
const int MAXK = 1007 ;

int n , m , k ;
string a , b ;
pii dp[ MAXK ][ 2 * MAXK ] , prv[ MAXK ][ 2 * MAXK ] ;

ll MOD[ 2 ] = { (ll)1e9 + 7 , 998244353 } ;
ll pw[ 2 ][ MAXN ] ;
ll base = 27 ;

struct hsh {
    ll val[ 2 ] ;
    hsh ( ) { val[ 0 ] = val[ 1 ] = 0 ; }
};

void init ( ) {
    pw[ 0 ][ 0 ] = pw[ 1 ][ 0 ] = 1 ;
    for ( int i = 1 ; i < MAXN ; ++ i ) {
        pw[ 0 ][ i ] = ( pw[ 0 ][ i - 1 ] * base ) % MOD[ 0 ] ;
        pw[ 1 ][ i ] = ( pw[ 1 ][ i - 1 ] * base ) % MOD[ 1 ] ;
    }
}

hsh pref[ 2 ][ MAXN ] ;

hsh get_hash ( int l , int r , int id ) {
    if ( l > r ) { return hsh ( ) ; }
    hsh ret = pref[ id ][ r ] ;
    hsh aux = pref[ id ][ l - 1 ] ;
    aux.val[ 0 ] = ( aux.val[ 0 ] * pw[ 0 ][ r - l + 1 ] ) % MOD[ 0 ] ;
    aux.val[ 1 ] = ( aux.val[ 1 ] * pw[ 1 ][ r - l + 1 ] ) % MOD[ 1 ] ;
    ret.val[ 0 ] = ( ret.val[ 0 ] + MOD[ 0 ] - aux.val[ 0 ] ) % MOD[ 0 ] ;
    ret.val[ 1 ] = ( ret.val[ 1 ] + MOD[ 1 ] - aux.val[ 1 ] ) % MOD[ 1 ] ;
    return ret ;
}

pii extend ( int x , int y ) {
    int l , r , mid ;
    l = 0 , r = min ( n - x , m - y ) ;
    while ( l < r ) {
        mid = ( l + r + 1 ) / 2 ;
        hsh aux1 = get_hash ( x + 1 , x + mid , 0 ) ;
        hsh aux2 = get_hash ( y + 1 , y + mid , 1 ) ;
        if ( aux1.val[ 0 ] == aux2.val[ 0 ] && aux1.val[ 1 ] == aux2.val[ 1 ] ) { l = mid ; }
        else { r = mid - 1 ; }
    }
    return { x + l , y + l } ;
}

void solve ( ) {
    cin >> n >> m >> k ;
    cin >> a >> b ;
    if ( abs ( n - m ) > k ) {
        cout << "NO\n" ;
        return ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        pref[ 0 ][ i ] = pref[ 0 ][ i - 1 ] ;
        pref[ 0 ][ i ].val[ 0 ] = ( base * pref[ 0 ][ i ].val[ 0 ] + ( a[ i - 1 ] - 'a' + 1 ) ) % MOD[ 0 ] ;
        pref[ 0 ][ i ].val[ 1 ] = ( base * pref[ 0 ][ i ].val[ 1 ] + ( a[ i - 1 ] - 'a' + 1 ) ) % MOD[ 1 ] ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        pref[ 1 ][ i ] = pref[ 1 ][ i - 1 ] ;
        pref[ 1 ][ i ].val[ 0 ] = ( base * pref[ 1 ][ i ].val[ 0 ] + ( b[ i - 1 ] - 'a' + 1 ) ) % MOD[ 0 ] ;
        pref[ 1 ][ i ].val[ 1 ] = ( base * pref[ 1 ][ i ].val[ 1 ] + ( b[ i - 1 ] - 'a' + 1 ) ) % MOD[ 1 ] ;
    }
    for ( int i = 0 ; i <= k + 1 ; ++ i ) {
        for ( int j = MAXK - k ; j <= MAXK + k ; ++ j ) {
            dp[ i ][ j ] = prv[ i ][ j ] = { -1 , -1 } ;
        }
    }
    dp[ 0 ][ MAXK ] = extend ( 0 , 0 ) ;
    for ( int lvl = 0 ; lvl < k ; ++ lvl ) {
        for ( int diff = -k ; diff <= k ; ++ diff ) {
            if ( dp[ lvl ][ diff + MAXK ].fi == -1 ) { continue ; }
            auto [ x , y ] = dp[ lvl ][ diff + MAXK ] ;
            {
                if ( x + 1 <= n && diff < k ) { 
                    auto [ nx , ny ] = extend ( x + 1 , y ) ;
                    if ( dp[ lvl + 1 ][ diff + MAXK + 1 ] < make_pair ( nx , ny ) ) {
                        dp[ lvl + 1 ][ diff + MAXK + 1 ] = { nx , ny } ;
                        prv[ lvl + 1 ][ diff + MAXK + 1 ] = { -1 , x + 1 } ;
                    }
                }
            }
            {
                if ( y + 1 <= m && diff > -k ) {
                    auto [ nx , ny ] = extend ( x , y + 1 ) ;
                    if ( dp[ lvl + 1 ][ diff + MAXK - 1 ] < make_pair ( nx , ny ) ) {
                        dp[ lvl + 1 ][ diff + MAXK - 1 ] = { nx , ny } ;
                        prv[ lvl + 1 ][ diff + MAXK - 1 ] = { 1 , x + 1 } ;
                    }
                }
            }
            {
                if ( x + 1 <= n && y + 1 <= m ) {
                    auto [ nx , ny ] = extend ( x + 1 , y + 1 ) ;
                    if ( dp[ lvl + 1 ][ diff + MAXK ] < make_pair ( nx , ny ) ) {
                        dp[ lvl + 1 ][ diff + MAXK ] = { nx , ny } ;
                        prv[ lvl + 1 ][ diff + MAXK  ] = { 0 , x + 1 } ;
                    }
                }
            }
        }
    }
    int act = n - m ;
    for ( int i = 0 ; i <= k ; ++ i ) {
        if ( dp[ i ][ act + MAXK ].fi == n ) {
            cout << "YES\n" ;
            vector < pair < pii , char > > ans ;
            int x = n , y = m , hh = i ;
            while ( x > 0 || y > 0 ) {
                if ( x > 0 && y > 0 && a[ x - 1 ] == b[ y - 1 ] ) {
                    -- x , -- y ;
                    continue ;
                }
                if ( prv[ hh ][ x - y + MAXK ].fi == -1 ) {
                    ans.push_back ( { prv[ hh ][ x - y + MAXK ] , 'a' } ) ;
                    -- x ;
                }
                else if ( prv[ hh ][ x - y + MAXK ].fi == 0 ) {
                    ans.push_back ( { prv[ hh ][ x - y + MAXK ] , b[ y - 1 ] } ) ;
                    -- x , -- y ;
                }
                else {
                    ans.push_back ( { prv[ hh ][ x - y + MAXK ] , b[ y - 1 ] } ) ;
                    -- y ;
                }
                -- hh ;
            }
            cout << (int)ans.size ( ) << "\n" ;
            for ( auto [ wh , c ] : ans ) {
                if ( wh.fi == -1 ) {
                    cout << "DELETE " << wh.se << "\n" ;
                }
                else if ( wh.fi == 0 ) {
                    cout << "REPLACE " << wh.se << " " << c << "\n" ;
                }
                else {
                    cout << "INSERT " << wh.se << " " << c << "\n" ;
                }
            }
            return ;
        }
    }
    cout << "NO\n" ;
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    init ( ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

詳細信息

Test #1:

score: 100
Accepted
time: 16ms
memory: 50344kb

input:

2
3 4 3
kot
plot
5 7 3
zycie
porazka

output:

YES
2
REPLACE 1 l
INSERT 1 p
NO

result:

ok OK!

Test #2:

score: 0
Accepted
time: 36ms
memory: 51440kb

input:

100
100 100 0
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
16 7 100
vvvvvvvvvvvvvvvv
qydopaq
37 33 43
ggggggggggggggggggggggggggggggggggggg
osk...

output:

YES
0
YES
16
DELETE 16
DELETE 15
DELETE 14
DELETE 13
DELETE 12
DELETE 11
DELETE 10
DELETE 9
DELETE 8
REPLACE 7 q
REPLACE 6 a
REPLACE 5 p
REPLACE 4 o
REPLACE 3 d
REPLACE 2 y
REPLACE 1 q
YES
28
DELETE 37
DELETE 36
DELETE 35
DELETE 34
REPLACE 33 o
REPLACE 32 o
REPLACE 31 a
REPLACE 30 a
REPLACE 27 p
REP...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 14032ms
memory: 81920kb

input:

100
3211 3185 685
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

YES
552
DELETE 3211
DELETE 3210
DELETE 3209
DELETE 3208
DELETE 3207
DELETE 3206
DELETE 3205
DELETE 3204
DELETE 3203
DELETE 3202
DELETE 3201
DELETE 3200
DELETE 3199
DELETE 3198
DELETE 3197
DELETE 3196
DELETE 3195
DELETE 3194
DELETE 3193
DELETE 3192
DELETE 3191
DELETE 3190
DELETE 3189
DELETE 3188
DELE...

result:

ok OK!

Test #4:

score: 0
Accepted
time: 12373ms
memory: 84116kb

input:

5
999000 998976 995
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

YES
894
DELETE 999000
DELETE 998999
DELETE 998998
DELETE 998997
DELETE 998996
DELETE 998995
DELETE 998994
DELETE 998993
DELETE 998992
DELETE 998991
DELETE 998990
DELETE 998989
DELETE 998988
DELETE 998987
DELETE 998986
DELETE 998985
DELETE 998984
DELETE 998983
DELETE 998982
DELETE 998981
DELETE 99898...

result:

ok OK!

Test #5:

score: 0
Accepted
time: 13947ms
memory: 84036kb

input:

5
999000 998971 1000
lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

NO
NO
NO
NO
NO

result:

ok OK!

Test #6:

score: -100
Wrong Answer
time: 6098ms
memory: 83580kb

input:

5
1000000 1000000 1000
faafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafa...

output:

YES
246
DELETE 2049
REPLACE 2046 a
DELETE 2043
DELETE 2039
DELETE 2037
DELETE 2031
DELETE 2029
DELETE 2027
DELETE 2025
DELETE 2015
DELETE 2013
DELETE 2011
DELETE 2009
DELETE 2007
DELETE 2005
DELETE 2003
DELETE 2001
DELETE 1953
REPLACE 1950 a
DELETE 1947
INSERT 1942 f
REPLACE 1938 a
INSERT 1937 f
DEL...

result:

wrong answer Test 1: final string is incorrect