結果

問題 No.513 宝探し２
コンテスト
ユーザー 0w1
提出日時 2017-05-12 17:55:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,181 bytes
コンパイル時間 1,983 ms
コンパイル使用メモリ 179,136 KB
実行使用メモリ 25,476 KB
平均クエリ数 61.25
最終ジャッジ日時 2024-07-16 13:39:53
合計ジャッジ時間 4,573 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 1 RE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:79:14: warning: 'ans_y' may be used uninitialized [-Wmaybe-uninitialized]
   79 |   assert( ask( ans_x, ans_y ) == 0 );
      |              ^
main.cpp:16:14: note: 'ans_y' was declared here
   16 |   int ans_x, ans_y;
      |              ^~~~~
main.cpp:79:14: warning: 'ans_x' may be used uninitialized [-Wmaybe-uninitialized]
   79 |   assert( ask( ans_x, ans_y ) == 0 );
      |              ^
main.cpp:16:7: note: 'ans_x' was declared here
   16 |   int ans_x, ans_y;
      |       ^~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int ask( int x, int y ) {
  cout << x << " " << y << endl;
  int d;
  cin >> d;
  if( d == 0 ) {
    exit( 0 );
  }
  return d;
}

signed main() {
  ios::sync_with_stdio( 0 );
  int ans_x, ans_y;
  {
    map< int, int > memo;
    int lb = 0, ub = int( 1e5 );
    while( ub - lb > 5 ) {
      int f = lb + ( ub - lb ) / 3;
      int g = lb + ( ub - lb ) / 3 * 2;
      int a = memo[ lb ] = ( memo.count( lb ) ? memo[ lb ] : ask( lb, 0 ) );
      int b = memo[ f ] = ( memo.count( f ) ? memo[ f ] : ask( f, 0 ) );
      int c = memo[ g ] = ( memo.count( g ) ? memo[ g ] : ask( g, 0 ) );
      int d = memo[ ub ] = ( memo.count( ub ) ? memo[ ub ] : ask( ub, 0 ) );
      if( a <= b and b <= c and c <= d ) {
        ub = f;
      } else if( a >= b and b <= c and c <= d ) {
        ub = g;
      } else if( a >= b and b >= c and c <= d ) {
        lb = f;
      } else if( a >= b and b >= c and c >= d ) {
        lb = g;
      } else {
        assert( 0 );
      }
    }
    int mind = int( 1e5 );
    for( int i = lb; i <= ub; ++i ) {
      int d = ask( i, 0 );
      if( d < mind ) {
        mind = d;
        ans_x = i;
      }
    }
  }
  {
    map< int, int > memo;
    int lb = 0, ub = int( 1e5 );
    while( ub - lb > 5 ) {
      int f = lb + ( ub - lb ) / 3;
      int g = lb + ( ub - lb ) / 3 * 2;
      int a = memo[ lb ] = ( memo.count( lb ) ? memo[ lb ] : ask( 0, lb ) );
      int b = memo[ f ] = ( memo.count( f ) ? memo[ f ] : ask( 0, f ) );
      int c = memo[ g ] = ( memo.count( g ) ? memo[ g ] : ask( 0, g ) );
      int d = memo[ ub ] = ( memo.count( ub ) ? memo[ ub ] : ask( 0, ub ) );
      if( a <= b and b <= c and c <= d ) {
        ub = f;
      } else if( a >= b and b <= c and c <= d ) {
        ub = g;
      } else if( a >= b and b >= c and c <= d ) {
        lb = f;
      } else if( a >= b and b >= c and c >= d ) {
        lb = g;
      } else {
        assert( 0 );
      }
    }
    int mind = int( 1e5 );
    for( int i = lb; i <= ub; ++i ) {
      int d = ask( 0, i );
      if( d < mind ) {
        mind = d;
        ans_y = i;
      }
    }
  }
  assert( ask( ans_x, ans_y ) == 0 );
  return 0;
}
0