結果

問題 No.850 企業コンテスト2位
ユーザー koba-e964koba-e964
提出日時 2019-07-09 09:50:08
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 2,112 bytes
コンパイル時間 977 ms
コンパイル使用メモリ 91,116 KB
実行使用メモリ 24,348 KB
平均クエリ数 200.14
最終ジャッジ日時 2023-09-23 17:50:43
合計ジャッジ時間 3,510 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
23,652 KB
testcase_01 AC 27 ms
23,916 KB
testcase_02 AC 26 ms
23,652 KB
testcase_03 AC 26 ms
23,532 KB
testcase_04 AC 25 ms
23,388 KB
testcase_05 AC 26 ms
23,496 KB
testcase_06 AC 26 ms
24,276 KB
testcase_07 AC 30 ms
24,348 KB
testcase_08 AC 32 ms
23,544 KB
testcase_09 AC 32 ms
23,544 KB
testcase_10 AC 37 ms
23,916 KB
testcase_11 AC 38 ms
23,388 KB
testcase_12 AC 37 ms
23,508 KB
testcase_13 AC 37 ms
23,616 KB
testcase_14 AC 37 ms
23,244 KB
testcase_15 AC 37 ms
23,292 KB
testcase_16 AC 36 ms
24,168 KB
testcase_17 AC 37 ms
23,604 KB
testcase_18 AC 37 ms
24,168 KB
testcase_19 AC 37 ms
23,964 KB
testcase_20 AC 38 ms
23,652 KB
testcase_21 AC 37 ms
23,388 KB
testcase_22 AC 36 ms
24,192 KB
testcase_23 AC 37 ms
24,192 KB
testcase_24 AC 37 ms
23,388 KB
testcase_25 AC 37 ms
23,964 KB
testcase_26 AC 37 ms
23,604 KB
testcase_27 AC 26 ms
23,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

const int N = 310;

int fst[N][N];
int snd[N][N];

int ask_lt(int x, int y) {
  assert (x != y);
  cout << "? " << x << " " << y << endl;
  int ans;
  cin >> ans;
  return ans;
}

int calc(int x, int y, int rank) {
  assert (x <= y);
  assert (rank == 1 || rank == 2);
  if (rank == 2 && snd[x][y] > 0) {
    return snd[x][y];
  }
  if (rank == 1) {
    if (fst[x][y] > 0) {
      return fst[x][y];
    }
    if (y == x) {
      return fst[x][y] = x;
    }
    if (y == x + 1) {
      int m = ask_lt(x, y);
      return fst[x][y] = m;
    }
    int mid = (x + y) / 2;
    int former = calc(x, mid, 1);
    int latter = calc(mid + 1, y, 1);
    int m = ask_lt(former, latter);
    return fst[x][y] = m;
  }
  // rank == 2
  if (snd[x][y] > 0) {
    return snd[x][y];
  }
  assert (x < y);
  assert (fst[x][y] > 0);
  if (y == x + 1) {
    int m = fst[x][y];
    return snd[x][y] = x + y - m;
  }
  int mid = (x + y) / 2;
  int former = calc(x, mid, 1);
  int latter = calc(mid + 1, y, 1);
  int m = fst[x][y];
  int ans;
  if (m == former) {
    int fs = calc(x, mid, 2);
    int m2 = ask_lt(fs, latter);
    ans = m2;
  } else {
    if (y > mid + 1) {
      int ls = calc(mid + 1, y, 2);
      int m2 = ask_lt(ls, former);
      ans = m2;
    } else {
      ans = former;
    }
  }
  return snd[x][y] = ans;
}


int main(void) {
  int n;
  cin >> n;
  REP(i, 0, N) {
    REP(j, 0, N) {
      fst[i][j] = -1;
      snd[i][j] = -1;
    }
  }
  calc(1, n, 1);
  int ans = calc(1, n, 2);
  cout << "! " << ans << endl;
}
0