Submission #3308827


Source Code Expand

/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-9-30 14:19:12
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

string C = "";
int cnt = 0;
bool que(int q) // (X/q) が奇数なら true
{
  assert(q % 2 == 1);
  cout << "? " << q << endl;
  string s;
  cin >> s;
  cnt++;
  return (s != C);
}

int main()
{
  cout << "? 2" << endl;
  cin >> C;
  int lb = 1;
  int ub = 1000000001;
  while (ub - lb > 2)
  {
    int t = (lb + ub) / 2;
    if (t % 2 == 0)
    {
      t++;
    }
    if (que(t))
    {
      lb = t;
    }
    else
    {
      ub = t;
    }
  }
  assert(cnt <= 30);
  cerr << "cnt = " << cnt << endl;
  if (C == "even")
  {
    cout << "! " << lb + 1 << endl;
  }
  else
  {
    cout << "! " << lb << endl;
  }
}

Submission Info

Submission Time
Task D - ロストテクノロジー
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1842 Byte
Status AC
Exec Time 6 ms
Memory 724 KB

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 40
Set Name Test Cases
All 00_small_case, 01_small_case, 02_small_case, 03_small_case, 04_small_case, 05_small_case, 06_small_case, 07_small_case, 08_small_case, 09_small_case, 10_neraiuti, 11_neraiuti, 12_neraiuti, 13_neraiuti, 14_neraiuti, 15_neraiuti, 16_neraiuti, 17_neraiuti, 18_neraiuti, 19_neraiuti, 20_large_case, 21_large_case, 22_large_case, 23_large_case, 24_large_case, 25_random_case, 26_random_case, 27_random_case, 28_random_case, 29_random_case, 30_random_case, 31_random_case, 32_random_case, 33_random_case, 34_random_case, 35_random_case, 36_random_case, 37_random_case, 38_random_case, 39_random_case
Case Name Status Exec Time Memory
00_small_case AC 5 ms 716 KB
01_small_case AC 5 ms 716 KB
02_small_case AC 5 ms 724 KB
03_small_case AC 5 ms 720 KB
04_small_case AC 5 ms 716 KB
05_small_case AC 5 ms 720 KB
06_small_case AC 5 ms 720 KB
07_small_case AC 5 ms 716 KB
08_small_case AC 5 ms 720 KB
09_small_case AC 6 ms 720 KB
10_neraiuti AC 5 ms 712 KB
11_neraiuti AC 5 ms 720 KB
12_neraiuti AC 5 ms 720 KB
13_neraiuti AC 5 ms 720 KB
14_neraiuti AC 5 ms 716 KB
15_neraiuti AC 5 ms 724 KB
16_neraiuti AC 5 ms 720 KB
17_neraiuti AC 5 ms 712 KB
18_neraiuti AC 5 ms 720 KB
19_neraiuti AC 5 ms 720 KB
20_large_case AC 5 ms 716 KB
21_large_case AC 5 ms 716 KB
22_large_case AC 5 ms 716 KB
23_large_case AC 5 ms 716 KB
24_large_case AC 5 ms 720 KB
25_random_case AC 5 ms 720 KB
26_random_case AC 5 ms 720 KB
27_random_case AC 5 ms 720 KB
28_random_case AC 5 ms 720 KB
29_random_case AC 5 ms 720 KB
30_random_case AC 5 ms 720 KB
31_random_case AC 5 ms 716 KB
32_random_case AC 5 ms 724 KB
33_random_case AC 5 ms 720 KB
34_random_case AC 5 ms 716 KB
35_random_case AC 5 ms 720 KB
36_random_case AC 5 ms 720 KB
37_random_case AC 5 ms 600 KB
38_random_case AC 5 ms 720 KB
39_random_case AC 5 ms 720 KB