QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#132663 | #5206. Hot and Cold | Swarthmore# | WA | 1ms | 3556kb | C++20 | 5.3kb | 2023-07-31 00:33:10 | 2023-07-31 00:33:12 |
Judging History
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);
}
}
}
详细
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