| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 530760 |
2022-02-26T17:09:51 Z |
pavement |
Aliens (IOI07_aliens) |
C++17 |
|
1 ms |
292 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, X, Y, M, lo, hi, rans, lans, tans, rcnt, rrig, ttop, posx, posy;
bool qry(int x, int y) {
if (x < 1 || y < 1 || x > N || y > N) return 0;
string ret;
cout << "examine " << x << ' ' << y << endl;
cin >> ret;
return ret == "true";
}
main() {
cin >> N >> X >> Y;
// go right
int k;
for (k = 0; ; k++)
if (!qry(X + (1 << k), Y)) break;
// boundary is within (2^(k-1), 2^k]
lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), rans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (!qry(X + mid, Y)) rans = mid, hi = mid - 1;
else lo = mid + 1;
}
cout << rans << '\n';
for (k = 0; ; k++)
if (!qry(X - (1 << k), Y)) break;
// boundary is within (2^(k-1), 2^k]
lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), lans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (!qry(X - mid, Y)) lans = mid, hi = mid - 1;
else lo = mid + 1;
}
for (k = 0; ; k++)
if (!qry(X, Y + (1 << k))) break;
// boundary is within (2^(k-1), 2^k]
lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), tans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (!qry(X, Y + mid)) tans = mid, hi = mid - 1;
else lo = mid + 1;
}
rans--, lans--, tans--;
M = rans + lans + 1;
X += rans;
Y += tans;
for (int k = -4; k <= 4; k++) {
bool tmp = qry(X + k * M, Y);
rcnt += tmp;
if (k > 0) rrig += tmp;
}
for (int k = 1; k <= 4; k++) {
bool tmp = qry(X, Y + k * M);
ttop += tmp;
}
if (rcnt == 2) {
posx = 5 - (1 + 2 * rrig);
posy = 5 - (1 + 2 * ttop);
} else {
assert(rcnt == 3);
posx = 5 - (2 * rrig);
posy = 5 - (2 * ttop);
}
X += (3 - posx) * M;
Y += (3 - posy) * M;
cout << "solution " << X - M / 2 << ' ' << Y - M / 2 << endl;
}
Compilation message
aliens.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
292 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
284 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
