QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#132663#5206. Hot and ColdSwarthmore#WA 1ms3556kbC++205.3kb2023-07-31 00:33:102023-07-31 00:33:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-31 00:33:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3556kb
  • [2023-07-31 00:33:10]
  • 提交

answer

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

// Template {{{
#define REP(n) for (int _=0; _<(n); _++)
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

namespace std {
  template<class Fun>
  class y_combinator_result {
    Fun fun_;
  public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
   
    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
      return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
  };
   
  template<class Fun>
  decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
  }
} // namespace std

#define DEBUG(x) cerr << #x << ": " << x << '\n'
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) { 
  return os << '(' << p.first << ", " << p.second << ')'; 
}
template<typename T_container, 
  typename T = typename enable_if<!is_same<T_container, string>::value, 
  typename T_container::value_type>::type> 
ostream& operator<<(ostream &os, const T_container &v) { 
  os << '['; string sep; 
  for (const T &x : v) 
    os << sep << x, sep = ", "; 
  return os << ']'; 
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}


int X, Y;
int cx = -1, cy = -1;
string found, closer, further, same, notfound;
int Q = 0;

const int MX = 1000000;
string CLOSER, FURTHER;
string query(int x, int y) {
  // Q++; assert(Q <= 64);
  cout << x << ' ' << y << endl;
  string s; cin >> s;
  // string s;
  // if (cx == -1 && cy == -1) {
  //   s = notfound;
  // }
  // else if (x == X && y == Y) {
  //   s = found;
  // }
  // else {
  //   ll d1 = 1LL * (cx - X) * (cx - X) + 1LL * (cy - Y) * (cy - Y);
  //   ll d2 = 1LL * (x - X) * (x - X) + 1LL * (y - Y) * (y - Y);
  //   cout << "d1: " << cx << ' ' << cy << ": " << d1 << endl;
  //   cout << "d2: " << x << ' ' << y << ": " << d2 << endl;
  //   if (d2 < d1) s = closer;
  //   else if (d2 > d1) s = further;
  //   else s = same;
  // }
  // cx = x, cy = y;

  for (char c: s) {
    if (c == '!') { // found it
      // cout << "FOUND " << x << ' ' << y << endl;
      exit(0);
    }
  }
  return s;
}

void bsearch(int xmin, int xmax, int ymin, int ymax) {
  assert(CLOSER.size() && FURTHER.size());
  cout << xmin << ' ' << xmax << ' ' << ymin << ' ' << ymax << endl;
  if (xmin == xmax && ymin == ymax) {
    query(xmin, ymin);
    return;
  }

  int new_xmin = xmin;
  int new_xmax = xmax;
  int new_ymin = ymin;
  int new_ymax = ymax;

  if (xmin == xmax) {
    string D = query(xmax, ymax);
    if (D == CLOSER) {
      new_ymin = (ymin + ymax) / 2 + 1;
    }
    else if (D == FURTHER) {
      new_ymax = (ymin + ymax - 1) / 2;
    }
    else { // equal
      assert((ymin + ymax) % 2 == 0);
      int mid = (ymin + ymax) / 2;
      new_ymin = new_ymax = mid;
    }
  }
  else if (ymin == ymax) {
    string B = query(xmax, ymin);
    if (B == CLOSER) {
      new_xmin = (xmin + xmax) / 2 + 1;
    }
    else if (B == FURTHER) {
      new_xmax = (xmin + xmax - 1) / 2;
    }
    else { // equal
      assert((xmin + xmax) % 2 == 0);
      int mid = (xmin + xmax) / 2;
      new_xmin = new_xmax = mid;
    }
  }
  else {
    string B = query(xmax, ymin);
    cout << "query B " << B << endl;
    if (B == CLOSER) {
      new_xmin = (xmin + xmax) / 2 + 1;
    }
    else if (B == FURTHER) {
      new_xmax = (xmin + xmax - 1) / 2;
    }
    else { // equal
      assert((xmin + xmax) % 2 == 0);
      int mid = (xmin + xmax) / 2;
      new_xmin = new_xmax = mid;
    }

    string D = query(xmax, ymax);
    cout << "query D " << D << endl;
    if (D == CLOSER) {
      new_ymin = (ymin + ymax) / 2 + 1;
    }
    else if (D == FURTHER) {
      new_ymax = (ymin + ymax - 1) / 2;
    }
    else { // equal
      assert((ymin + ymax) % 2 == 0);
      int mid = (ymin + ymax) / 2;
      new_ymin = new_ymax = mid;
    }
  }
  query(new_xmin, new_ymin);
  bsearch(new_xmin, new_xmax, new_ymin, new_ymax);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  // cin >> X >> Y;
  // cin >> found >> closer >> further >> same >> notfound;

  string not_found = query(1, 0);
  string x1 = query(0, 0);
  string y2 = query(0, 1);
  string y1 = query(0, 0);

  // cout << x1 << ' ' << y1 << ' ' << y2 << endl;

  if (x1 == y1) {
    FURTHER = x1;
    CLOSER = y2;
    bsearch(0, MX, 0, MX);
  }
  else {
    // on x or y-axis
    // check corners first
    // total: 8 + 40 queries
    query(0, MX);
    query(MX, 0);
    query(MX, MX);
    CLOSER = query(MX, MX-1);

    if (CLOSER == y2) {
      FURTHER = y1;
      query(0, 0);
      bsearch(0, 0, 1, MX-1);
    }
    else {
      assert(CLOSER == y1);
      FURTHER = y2;
      query(0, 0);
      bsearch(1, MX-1, 0, 0);
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3556kb

input:

Tabilmadi
Dalej
Daha yakin
Dalej
Dalej
Daha yakin
Dalej
Daha yakin
Daha yakin
Dalej
Daha yakin
Dalej
Daha yakin
Dalej
Daha yakin
Dalej
Daha yakin
Dalej
Daha yakin
Dalej
Daha yakin
Dalej
Daha yakin
Dalej

output:

1 0
0 0
0 1
0 0
0 1000000
1000000 0
1000000 1000000
1000000 999999
0 0
1 999999 0 0
999999 0
1 0
1 499999 0 0
499999 0
1 0
1 249999 0 0
249999 0
125000 0
125000 125000 0 0
125000 0

result:

wrong answer format  Unexpected end of file - int32 expected