fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4.  
  5. #define sz(v) (int)v.size()
  6. #define ll long long
  7. #define all(v)  v.begin() , v.end()
  8. #define rall(v)  v.rbegin() , v.rend()
  9. #define pf push_front
  10. #define pb push_back
  11. #define fast FastInputOutput() ;
  12. #define Clear( container , value ) memset( container , value , sizeof container )
  13. #define PI acos( -1.0 )
  14. #define c_b fflush(stdin);
  15.  
  16. int dx[ ] = { 0 , 0 , -1 , 1 , 1 , -1 , 1 , 1 } ;
  17. int dy[ ] = { -1 , 1 , 0 , 0 , 1 , -1 ,-1 ,-1 } ;
  18.  
  19. void File_input( string pathIn , string pathOut ) {
  20.     freopen( pathIn.c_str() , "r", stdin ) ;
  21.     freopen( pathOut.c_str() , "w", stdout ) ;
  22. }
  23.  
  24. int msg(){
  25.         srand( time( 0 ) ) ;
  26.         vector < string > st = {
  27.         "Wish everyone high ratings!",
  28.         "Good luck!",
  29.         "Have fun!",
  30.         "Please, read all the problems!",
  31.         "Go Go fight!" } ;
  32.         cerr << st[ rand() % sz( st ) ] ;
  33.    return 0 ;
  34. }
  35.  
  36. void FastInputOutput() {
  37.     ios_base :: sync_with_stdio( 0 ) ;
  38.     cin.tie( 0 ) ;
  39.     cout.tie( 0 ) ;
  40. }
  41.  
  42. int n , m ;
  43. const int N = 52 ;
  44. int a[ N ][ N ] , b[ N ][ N ] ;
  45. bool aa[ N ][ N ] , bb[ N ][ N ] ;
  46.  
  47.  
  48. bool valid( int x , int y ){
  49. return x >= 0 && x < n && y >= 0 && y < m ;
  50. }
  51.  
  52.  
  53. int Try( int a[ N ][ N ] , int i , int j ){
  54.        if( valid( i , j + 1 ) )
  55.            if( a[ i ][ j + 1 ] <= a[ i ][ j ] ){
  56.               return 0 ;
  57.            }
  58.  
  59.        if( valid( i + 1 , j ) )
  60.            if( a[ i + 1 ][ j ] <= a[ i ][ j ] ){
  61.               return 0 ;
  62.            }
  63.  
  64.        if( valid( i , j - 1 ) )
  65.            if( a[ i ][ j - 1 ] >= a[ i ][ j ] ){
  66.               return 0 ;
  67.            }
  68.  
  69.       if( valid( i - 1 , j ) )
  70.            if( a[ i - 1 ][ j ] >= a[ i ][ j ] ){
  71.               return 0 ;
  72.            }
  73.      return 1 ;
  74. }
  75.  
  76. int main(){
  77.  
  78.   cin >> n >> m ;
  79.   for( int i = 0 ; i < n ; i++ ){
  80.     for( int j = 0 ; j < m ; j++ ){
  81.         cin >> a[ i ][ j ] ;
  82.     }
  83.   }
  84.  
  85.   for( int i = 0 ; i < n ; i++ ){
  86.     for( int j = 0 ; j < m ; j++ ){
  87.         cin >> b[ i ][ j ] ;
  88.     }
  89.   }
  90.  
  91.   int x , y , cnt ;
  92.   vector < pair < int , int > > is ;
  93.   bool flage = 0;
  94.   for( int ran = 0 ; ran < 3e3 ; ran++ ){
  95.  
  96.      for( int i = 0 ; i < n ; i++ ){
  97.         for( int j = 0 ; j < m ; j++ ){
  98.             x = -1 , y = -1 ;
  99.             cnt = 0 ;
  100.             if( j > 0 ){
  101.                 x = a[ i ][ j - 1 ] ;
  102.             }
  103.  
  104.             if( i > 0 ){
  105.                 y = a[ i - 1 ][ j ] ;
  106.             }
  107.  
  108.             if( a[ i ][ j ] > x ){
  109.                 cnt++ ;
  110.             }
  111.  
  112.             if( a[ i ][ j ] > y ){
  113.                 cnt++ ;
  114.             }
  115.  
  116.             if( valid( i , j + 1 ) && a[ i ][ j ] < a[ i ][ j + 1 ] ){
  117.                 cnt++ ;
  118.             }
  119.  
  120.             if( valid( i + 1 , j ) && a[ i ][ j ] < a[ i + 1 ][ j ] ){
  121.                 cnt++ ;
  122.             }
  123.  
  124.             if( !valid( i + 1 , j ) )
  125.                 cnt++ ;
  126.  
  127.             if( !valid( i , j + 1 ) )
  128.                 cnt++ ;
  129.  
  130.             if( cnt < 4 ){
  131.  
  132.             cnt = 0 ;
  133.  
  134.             if( b[ i ][ j ] > x ){
  135.                 cnt++ ;
  136.                 //cout << 1 << "\n" ;
  137.             }
  138.  
  139.             if( b[ i ][ j ] > y ){
  140.                 cnt++ ;
  141.                 //cout << 2 << "\n" ;
  142.             }
  143.  
  144.             if( valid( i , j + 1 ) && b[ i ][ j ] < a[ i ][ j + 1 ] ){
  145.                 cnt++ ;
  146.                 //cout << 3 << "\n" ;
  147.             }
  148.  
  149.             if( valid( i + 1 , j ) && b[ i ][ j ] < a[ i + 1 ][ j ] ){
  150.                 cnt++ ;
  151.                 //cout << 4 << "\n" ;
  152.             }
  153.  
  154.             if( !valid( i + 1 , j ) )
  155.                 cnt++ ;
  156.  
  157.             if( !valid( i , j + 1 ) )
  158.                 cnt++ ;
  159.  
  160.  
  161.  
  162.             if( cnt == 4 )
  163.              swap( a[ i ][ j ] , b[ i ][ j ] ) ;
  164.             }
  165.  
  166.  
  167.  
  168.  
  169.         }
  170.      }
  171.  
  172.  
  173.  
  174.  
  175.  
  176.      for( int i = 0 ; i < n ; i++ ){
  177.         for( int j = 0 ; j < m ; j++ ){
  178.             x = -1 , y = -1 ;
  179.             cnt = 0 ;
  180.             if( j > 0 ){
  181.                 x = b[ i ][ j - 1 ] ;
  182.             }
  183.  
  184.             if( i > 0 ){
  185.                 y = b[ i - 1 ][ j ] ;
  186.             }
  187.  
  188.             if( b[ i ][ j ] > x ){
  189.                 cnt++ ;
  190.             }
  191.  
  192.             if( b[ i ][ j ] > y ){
  193.                 cnt++ ;
  194.             }
  195.  
  196.             if( valid( i , j + 1 ) && b[ i ][ j ] < b[ i ][ j + 1 ] ){
  197.                 cnt++ ;
  198.             }
  199.  
  200.             if( valid( i + 1 , j ) && b[ i ][ j ] < b[ i + 1 ][ j ] ){
  201.                 cnt++ ;
  202.             }
  203.  
  204.             if( cnt < 4 ){
  205.  
  206.             cnt = 0 ;
  207.  
  208.             if( a[ i ][ j ] > x ){
  209.                 cnt++ ;
  210.                 //cout << 1 << "\n" ;
  211.             }
  212.  
  213.             if( a[ i ][ j ] > y ){
  214.                 cnt++ ;
  215.                 //cout << 2 << "\n" ;
  216.             }
  217.  
  218.             if( valid( i , j + 1 ) && a[ i ][ j ] < b[ i ][ j + 1 ] ){
  219.                 cnt++ ;
  220.                 //cout << 3 << "\n" ;
  221.             }
  222.  
  223.             if( valid( i + 1 , j ) && a[ i ][ j ] < b[ i + 1 ][ j ] ){
  224.                 cnt++ ;
  225.                 //cout << 4 << "\n" ;
  226.             }
  227.  
  228.             if( !valid( i + 1 , j ) )
  229.                 cnt++ ;
  230.  
  231.             if( !valid( i , j + 1 ) )
  232.                 cnt++ ;
  233.  
  234.  
  235.  
  236.             if( cnt == 4 )
  237.              swap( a[ i ][ j ] , b[ i ][ j ] ) ;
  238.             }
  239.  
  240.  
  241.  
  242.  
  243.         }
  244.      }
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.   }
  254.  
  255.  // puts("Impossible") ;
  256.  
  257.  
  258.   for( int i = 0 ; i < n ; i++ ){
  259.      for( int j = 0 ; j < m ; j++ ){
  260.  
  261.              if( j > 0 ){
  262.                 x = b[ i ][ j - 1 ] ;
  263.             }
  264.  
  265.             if( i > 0 ){
  266.                 y = b[ i - 1 ][ j ] ;
  267.             }
  268.  
  269.             if( b[ i ][ j ] > x ){
  270.                 cnt++ ;
  271.             }
  272.  
  273.             if( b[ i ][ j ] > y ){
  274.                 cnt++ ;
  275.             }
  276.  
  277.             if( valid( i , j + 1 ) && b[ i ][ j ] < b[ i ][ j + 1 ] ){
  278.                 cnt++ ;
  279.             }
  280.  
  281.             if( valid( i + 1 , j ) && b[ i ][ j ] < b[ i + 1 ][ j ] ){
  282.                 cnt++ ;
  283.             }
  284.  
  285.             if( !valid( i + 1 , j ) )
  286.                 cnt++ ;
  287.  
  288.             if( !valid( i , j + 1 ) )
  289.                 cnt++ ;
  290.  
  291.             if( cnt >= 4 ){
  292.                 aa[ i ][ j ] = 1 ;
  293.             }
  294.      }
  295.   }
  296.  
  297.  
  298.  
  299.   for( int i = 0 ; i < n ; i++ ){
  300.      for( int j = 0 ; j < m ; j++ ){
  301.          if( !Try( a , i , j ) ){
  302.             puts("Impossible") ;
  303.             return 0 ;
  304.          }
  305.          if( !Try( b , i , j ) ){
  306.             puts("Impossible") ;
  307.             return 0 ;
  308.          }
  309.      }
  310.   }
  311.  
  312.  
  313.   puts("Possible") ;
  314.  
  315.  
  316.  
  317.  
  318.  
  319.   return 0;
  320. }
  321.  
  322.  
Success #stdin #stdout 0s 15264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Possible
https://ideone.com/JpJND4
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!