QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132665#5206. Hot and ColdSwarthmore#RE 0ms0kbC++205.2kb2023-07-31 00:36:022023-07-31 00:36:04

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:36:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-31 00:36:02]
  • 提交

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;
  getline(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;

  if (s.back() == '!') {
    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);
    }
  }
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

Tabilmadi
Dalej
Daha yakin
Dalej
Dalej
Sama distanco
Daha yakin

output:

1 0
0 0
0 1
0 0
0 1000000 0 1000000
1000000 0
query B Dalej
1000000 1000000
query D Sama distanco
0 500000
0 499999 500000 500000
499999 500000

result: