結果

問題 No.850 企業コンテスト2位
ユーザー koba-e964koba-e964
提出日時 2019-07-09 09:50:08
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 2,112 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 95,580 KB
実行使用メモリ 25,476 KB
平均クエリ数 200.14
最終ジャッジ日時 2024-07-16 17:44:21
合計ジャッジ時間 3,133 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
25,220 KB
testcase_01 AC 21 ms
25,220 KB
testcase_02 AC 20 ms
25,220 KB
testcase_03 AC 21 ms
24,964 KB
testcase_04 AC 21 ms
24,836 KB
testcase_05 AC 21 ms
24,836 KB
testcase_06 AC 22 ms
24,836 KB
testcase_07 AC 25 ms
25,092 KB
testcase_08 AC 27 ms
25,220 KB
testcase_09 AC 25 ms
24,964 KB
testcase_10 AC 31 ms
24,964 KB
testcase_11 AC 30 ms
24,964 KB
testcase_12 AC 31 ms
24,836 KB
testcase_13 AC 30 ms
24,836 KB
testcase_14 AC 31 ms
24,836 KB
testcase_15 AC 30 ms
24,580 KB
testcase_16 AC 33 ms
24,964 KB
testcase_17 AC 29 ms
24,580 KB
testcase_18 AC 30 ms
24,964 KB
testcase_19 AC 30 ms
25,220 KB
testcase_20 AC 32 ms
24,964 KB
testcase_21 AC 31 ms
24,568 KB
testcase_22 AC 29 ms
25,220 KB
testcase_23 AC 31 ms
25,220 KB
testcase_24 AC 30 ms
24,580 KB
testcase_25 AC 29 ms
25,476 KB
testcase_26 AC 32 ms
25,220 KB
testcase_27 AC 24 ms
24,940 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