BoxerTC

Untitled

Jun 7th, 2015
328
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.41 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 pb push_back
  9. #define all(v) v.begin() , v.end()
  10. #define SZ(v) ((int)(v).size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.    
  16. #define N 100
  17. #define INF (1<<20)
  18.  
  19. typedef long long ll;
  20. typedef long double ld;
  21. typedef pair< int , int > pii;
  22. typedef vector< pii > vpii;
  23. typedef vector< int > vi;
  24. typedef vector< vi > vvi;
  25.  
  26.  
  27. int main(){
  28.     int cases;
  29.     sc( cases );
  30.     REP( tc , cases ){
  31.         int n;
  32.         sc( n );
  33.         vi F( n );
  34.         REP( j , 2 ) {
  35.             REP( i , n - 2 ){
  36.                 int x;
  37.                 sc( x );
  38.                 x --;
  39.                 F[ x ] ++;
  40.             }
  41.         }
  42.         /*
  43.         if( n == 3 ){
  44.             puts( "none" );
  45.             puts( "3 1" );
  46.             puts( "2 1" );
  47.             continue;
  48.         }*/
  49.         vpii vec;
  50.        
  51.         REP( i , n - 2 )
  52.             vec.pb( mp( F[ i ] , i ) );
  53.         sort( all( vec ) );
  54.        
  55.         vpii vec2;
  56.         REP( i , min( 2 , SZ( vec ) ) )
  57.             vec2.pb( vec[ i ] );
  58.         REP( i , min( 2 , SZ( vec ) ) )
  59.             vec2.pb( vec[ SZ( vec ) - 1 - i ] );
  60.        
  61.         sort( all( vec2 ) );
  62.         vec2.resize( unique( all( vec2 ) ) - vec2.begin() );
  63.         REP( i , 2 )
  64.             vec2.pb( mp( F[ n - 1 - i ] , n - 1 - i ) );
  65.        
  66.        
  67.         int best = -1;
  68.         vi x( 2 ) , y( 2 );
  69.         REP( i , SZ( vec2 ) )
  70.             REP( j , SZ( vec2 ) )
  71.                 REP( k , SZ( vec2 ) ){
  72.                     if( i == j ) continue;
  73.                     if( i == k ) continue;
  74.                     if( j == k ) continue;
  75.                     if( (vec2[ k ].se == n - 1) || (vec2[ k ].se == n - 2) ) continue;
  76.                     vec2[ i ].fi ++;
  77.                     vec2[ j ].fi ++;
  78.                     vec2[ k ].fi += 2;
  79.                    
  80.                     int maxi = 0 , mini = INT_MAX;
  81.                     REP( p , SZ( vec2 ) ){
  82.                         maxi = max( maxi , vec2[ p ].fi );
  83.                         mini = min( mini , vec2[ p ].fi );
  84.                     }
  85.                     //cout << mini << " " << maxi << endl;
  86.                     int cnt = 0;
  87.                     if( vec2[ SZ(vec2) - 1 ].fi != maxi && vec2[ SZ(vec2) - 1 ].fi != mini ) cnt ++;
  88.                     if( vec2[ SZ(vec2) - 2 ].fi != maxi && vec2[ SZ(vec2) - 2 ].fi != mini ) cnt ++;
  89.                    
  90.                     if( cnt > best ){
  91.                         best = cnt;
  92.                         x[ 0 ] = vec2[ i ].se , x[ 1 ] = vec2[ k ].se;
  93.                         y[ 0 ] = vec2[ j ].se , y[ 1 ] = vec2[ k ].se;
  94.                     }
  95.                     vec2[ i ].fi --;
  96.                     vec2[ j ].fi --;
  97.                     vec2[ k ].fi -= 2;
  98.                 }
  99.         if( best == 0 ) puts( "none" );
  100.         else if( best == 1 ) puts( "one" );
  101.         else puts( "both" );
  102.         printf( "%d %d\n" , x[ 0 ] + 1 , x[ 1 ] + 1 );
  103.         printf( "%d %d\n" , y[ 0 ] + 1 , y[ 1 ] + 1 );
  104.        
  105.     }  
  106. }
Advertisement
Add Comment
Please, Sign In to add comment