| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 54307 |
2018-07-03T06:37:34 Z |
강태규(#1471) |
Aliens (IOI07_aliens) |
C++11 |
|
4 ms |
616 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n, sx, sy;
int query(llong x, llong y) {
static map<pii, int> mp;
static char s[100];
if (x < 1 || n < x || y < 1 || n < y) return 0;
if (mp.find(pii(x, y)) != mp.end()) return mp[pii(x, y)];
printf("examine %lld %lld\n", x, y);
fflush(stdout);
scanf("%s", s);
return mp[pii(x, y)] = (s[0] == 't');
}
int main() {
scanf("%d%d%d", &n, &sx, &sy);
llong lt = 0, rt = 0, ut = 0, dt = 0, t = 0;
{
llong s = 1, e = sx - 1, ans = sx;
while (s <= e) {
llong m = (s + e) / 2;
if (query(m, sy)) ans = m, e = m - 1;
else s = m + 1;
}
lt = ans;
if (query((ans + sx) / 2, sy)) {
if (!query(ans + (sx - ans) / 4, sy)) {
s = (ans + sx) / 2 + 1, e = ans + (sx - ans) / 4 - 1;
llong ans2 = (ans + sx) / 2;
while (s <= e) {
llong m = (s + e) / 2;
if (query(m, sy)) ans2 = m, e = m - 1;
else s = m + 1;
}
t = ans2 - ans;
}
}
else {
s = (ans + sx) / 2 + 1, e = sx - 1;
llong ans2 = sx;
while (s <= e) {
llong m = (s + e) / 2;
if (query(m, sy)) ans2 = m, e = m - 1;
else s = m + 1;
}
t = ans2 - ans;
}
}
{
llong s = sx + 1, e = n, ans = sx;
while (s <= e) {
llong m = (s + e) / 2;
if (query(m, sy)) ans = m, s = m + 1;
else e = m - 1;
}
rt = ans;
if (query((ans + sx) / 2, sy)) {
if (!query(ans - (ans - sx) / 4, sy)) {
s = ans - (ans - sx) / 4 + 1, e = (ans + sx) / 2 - 1;
llong ans2 = (ans + sx) / 2;
while (s <= e) {
llong m = (s + e) / 2;
if (query(m, sy)) ans2 = m, s = m + 1;
else e = m - 1;
}
t = ans - ans2;
}
}
else {
s = sx + 1, e = (ans + sx) / 2 - 1;
llong ans2 = sx;
while (s <= e) {
llong m = (s + e) / 2;
if (query(m, sy)) ans2 = m, s = m + 1;
else e = m - 1;
}
t = ans - ans2;
}
}
{
llong s = 1, e = sy - 1, ans = sy;
while (s <= e) {
llong m = (s + e) / 2;
if (query(sx, m)) ans = m, e = m - 1;
else s = m + 1;
}
ut = ans;
if (query(sx, (ans + sy) / 2)) {
if (!query(sx, ans + (sy - ans) / 4)) {
s = (ans + sy) / 2 + 1, e = ans + (sy - ans) / 4 - 1;
llong ans2 = (ans + sy) / 2;
while (s <= e) {
llong m = (s + e) / 2;
if (query(sx, m)) ans2 = m, e = m - 1;
else s = m + 1;
}
t = ans2 - ans;
}
}
else {
s = (ans + sy) / 2 + 1, e = sy - 1;
llong ans2 = sy;
while (s <= e) {
llong m = (s + e) / 2;
if (query(sx, m)) ans2 = m, e = m - 1;
else s = m + 1;
}
t = ans2 - ans;
}
}
{
llong s = sy + 1, e = n, ans = sy;
while (s <= e) {
llong m = (s + e) / 2;
if (query(sx, m)) ans = m, s = m + 1;
else e = m - 1;
}
dt = ans;
if (query(sx, (ans + sy) / 2)) {
if (!query(sx, ans - (ans - sy) / 4)) {
s = ans - (ans - sy) / 4 + 1, e = (ans + sy) / 2 - 1;
llong ans2 = (ans + sy) / 2;
while (s <= e) {
llong m = (s + e) / 2;
if (query(sx, m)) ans2 = m, s = m + 1;
else e = m - 1;
}
t = ans - ans2;
}
}
else {
s = sy + 1, e = (ans + sy) / 2 - 1;
llong ans2 = sy;
while (s <= e) {
llong m = (s + e) / 2;
if (query(sx, m)) ans2 = m, s = m + 1;
else e = m - 1;
}
t = ans - ans2;
}
}
if (!t) t = rt - lt + 1;
while (query(lt - t, sy)) lt -= t;
while (query(rt + t, sy)) rt += t;
while (query(sx, ut - t)) ut -= t;
while (query(sx, dt + t)) dt += t;
printf("solution %lld %lld\n", (lt + rt) / 2, (ut + dt) / 2);
return 0;
}
Compilation message
aliens.cpp: In function 'int query(llong, llong)':
aliens.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &sx, &sy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
408 KB |
Output is correct |
| 2 |
Correct |
2 ms |
408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
584 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
584 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
616 KB |
Incorrect |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
616 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
616 KB |
Incorrect |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
616 KB |
Output is correct |
| 2 |
Correct |
3 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
616 KB |
Output is correct |
| 2 |
Correct |
4 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
616 KB |
Output is correct |
| 2 |
Correct |
3 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
616 KB |
Output is correct |
| 2 |
Correct |
3 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
