QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107323 | #850. Edit Distance Yet Again | Sorting | WA | 14032ms | 84116kb | C++20 | 5.7kb | 2023-05-20 23:13:01 | 2023-05-20 23:13:03 |
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 = 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