BoxerTC

Untitled

Jun 22nd, 2015
414
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.78 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; i++ )
  6. #define clr( t , val ) memset( t , val , sizeof(t) )
  7.  
  8. #define all(v)  v.begin() , v.end()
  9. #define pb push_back
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.  
  16. #define test() cout << "hola q hace" << endl;
  17. #define DEBUG( x ) cerr <<  #x << "=" << x << endl;
  18. #define DEBUG2( x , y ) cerr << #x << "=" << x << " " << #y << "=" << y << endl;
  19.  
  20.  
  21. typedef long long ll;
  22. typedef vector< ll > vll;
  23. typedef pair< int , int > pii;
  24. typedef vector< pii > vpii;
  25. typedef vector< vpii > vvpii;
  26. typedef vector< vvpii > vvvpii;
  27. typedef vector< int > vi;
  28. typedef vector< vi > vvi;
  29. typedef vector< vvi > vvvi;
  30. typedef vector< vvvi > vvvvi;
  31.  
  32. void fix( string &s ){
  33.     for( auto &x : s ) x -= 'A' - 1;
  34. }
  35. ll POT[ 2 ][ 40 * 40 + 5 ];
  36. vi MOD = {1000000007LL , 1000000009LL};
  37. vvvi generate( vi &v , int n ){
  38.     vvvi T( n , vvi( n ) );
  39.     for( int i = 0 ; i < n ; ++i ){
  40.         vi H( 2 );
  41.         for( int j = i ; j < n ; ++j ){
  42.             REP( k , 2 ) H[ k ] = ((ll)H[ k ] * 31LL + v[ j ])%MOD[ k ];
  43.             T[ i ][ j ] = H;
  44.         }
  45.     }
  46.     return T;
  47. }
  48. void mySort( vpii &a , vpii &b ){
  49.     vector< pair< pii , pii > > v;
  50.     REP( i , SZ(a) ) v.pb( mp(a[ i ] , b[ i ]) );
  51.     sort( all( v ) );
  52.     REP( i , SZ(a) ) a[ i ] = v[ i ].fi , b[ i ] = v[ i ].se;
  53. }
  54.  
  55. void generate( vvi &T , int n , int m , vvvpii &R , vvvpii &S ){
  56.     vvvvi P( n );
  57.     //test();
  58.    
  59.     REP( i , n ) P[ i ] = generate( T[ i ] , m );  
  60.     R = vvvpii( n + 1 , vvpii( m + 1 ) );
  61.     S = vvvpii( n + 1 , vvpii( m + 1 ) );
  62.    
  63.     for( int X1 = 0 ; X1 < m ; ++X1 )
  64.         for( int X2 = X1 ; X2 < m ; ++X2 ){
  65.             int len2 = X2 - X1 + 1;    
  66.             vll b = { POT[ 0 ][ len2 ] , POT[ 1 ][ len2 ] };
  67.             for( int Y1 = 0 ; Y1 < n ; ++Y1 ){
  68.                 vll H( 2 );
  69.                 for( int Y2 = Y1 ; Y2 < n ; ++Y2 ){
  70.                     REP( i , 2 )
  71.                         H[ i ] = ((ll)H[ i ] * b[ i ] + P[ Y2 ][ X1 ][ X2 ][ i ] )%MOD[ i ];
  72.                    
  73.                     int len1 = Y2 - Y1 + 1;
  74.                     R[ len1 ][ len2 ].pb( mp( H[ 0 ] , H[ 1 ] ) );
  75.                     S[ len1 ][ len2 ].pb( mp( Y1 , X1 ) );
  76.                 }
  77.             }
  78.         }
  79.    
  80.     REP( i , n + 1 ) REP( j , m + 1 ) mySort( R[ i ][ j ] , S[ i ][ j ] );
  81. }
  82. int main(){
  83.    
  84.     REP( i , 2 ) POT[ i ][ 0 ] = 1;
  85.     REP( i , 2 )for( int len = 1 ; len <= 40 * 40 ; ++len )
  86.         POT[ i ][ len ] = (POT[ i ][ len - 1 ] * 31LL)%MOD[ i ];
  87.    
  88.     freopen( "money.in" , "r" , stdin );
  89.     freopen( "money.out" , "w" , stdout );
  90.    
  91.     vvi coord( 2 , vi( 2 ) );
  92.     while( cin >> coord[ 0 ][ 0 ] ){
  93.         vvvi T( 2 );
  94.         REP( i , 2 ){
  95.             REP( j , 2 ) {
  96.                 if( !i && !j ) continue;
  97.                 cin >> coord[ i ][ j ];
  98.             }
  99.             string s;
  100.             REP( a , coord[ i ][ 0 ] ) {
  101.                 cin >> s;
  102.                 fix( s );
  103.                 vi vec( all( s ) );
  104.                 T[ i ].pb( vec );
  105.             }
  106.         }
  107.         vector< vvvpii > P( 2 );
  108.         vector< vvvpii > I( 2 );
  109.         REP( i , 2 ) generate( T[ i ] , coord[ i ][ 0 ] , coord[ i ][ 1 ] , P[ i ] , I[ i ] );
  110.  
  111.         int maxi = 0;
  112.         int t = 0;
  113.         pii p1 , p2 , p;
  114.         for( int i = 0 ; i <= min( coord[ t ][ 0 ] , coord[ t ^ 1 ][ 0 ] ) ; ++i )
  115.             for( int j = 0 ; j <= min( coord[ t ][ 1 ] , coord[ t ^ 1 ][ 1 ] ) ; ++j )
  116.                 REP( k , SZ( P[ t ][ i ][ j ] ) ){
  117.                     auto x = P[ t ][ i ][ j ][ k ];
  118.                     if( binary_search( all( P[ t ^ 1 ][ i ][ j ] ) , x ) ){
  119.                         if( i * j <= maxi ) continue;
  120.                         maxi = i * j;
  121.                         p = mp( i , j );
  122.                         auto vec = P[ t ^ 1 ][ i ][ j ];
  123.                         int pos = lower_bound( all( vec ) , x ) - vec.begin();
  124.                         p1 = I[ t ][ i ][ j ][ k ];
  125.                         p2 = I[ t ^ 1 ][ i ][ j ][ pos ];
  126.                     }
  127.                 }
  128.         if( maxi == 0 ){
  129.             puts( "0 0" );
  130.             continue;
  131.         }
  132.         printf( "%d %d\n" , (int)p.fi , (int)p.se );
  133.         printf( "%d %d\n" , (int)(p1.fi + 1) , (int)(p1.se + 1) );
  134.         printf( "%d %d\n" , (int)(p2.fi + 1) , (int)(p2.se + 1) );
  135.     }
  136.    
  137. }
Advertisement
Add Comment
Please, Sign In to add comment