QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #107318 | #850. Edit Distance Yet Again | Sorting | RE | 40ms | 51200kb | C++20 | 5.6kb | 2023-05-20 22:53:30 | 2023-05-20 22:53:32 |
Judging History
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 = 26 ;
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 ;
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' ) ) % MOD[ 0 ] ;
pref[ 0 ][ i ].val[ 1 ] = ( base * pref[ 0 ][ i ].val[ 1 ] + ( a[ i - 1 ] - 'a' ) ) % 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' ) ) % MOD[ 0 ] ;
pref[ 1 ][ i ].val[ 1 ] = ( base * pref[ 1 ][ i ].val[ 1 ] + ( b[ i - 1 ] - 'a' ) ) % MOD[ 1 ] ;
}
for ( int i = 0 ; i <= k + 1 ; ++ i ) {
for ( int j = MAXK - k ; j <= MAXK + k ; ++ j ) {
dp[ 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: 18ms
memory: 50984kb
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: 40ms
memory: 51200kb
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: -100
Runtime Error
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...