#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int N;
struct P{
ll x, y;
};
P ans;
P st;
struct SQ{
P lu, rd;
P mid;
void cmid(){
mid.x=(lu.x+rd.x)/2;
mid.y=(lu.y+rd.y)/2;
}
};
vector<P> v(1);
string str;
set<pair<ll, ll>> s;
map<pair<ll, ll>, bool> mp;
char c[100];
bool chk(ll x, ll y){
if(x<1 || x>N || y<1 || y>N) return true;
return false;
}
bool examine(ll x, ll y){
if(chk(x, y)) return false;
if(mp.find(make_pair(x, y))==mp.end()){
printf("examine %lld %lld\n", x, y);
fflush(stdout);
scanf("%s", c);
mp[make_pair(x, y)] = (c[0]=='t');
}
return mp[make_pair(x, y)];
}
bool examin(P a){
return examine(a.x, a.y);
}
SQ now;
int main(){
scanf("%d%lld%lld", &N, &st.x, &st.y);
ll t=1, ss, ee, mi;
P a=st;
if(!examine(a.x, a.y+1)){
now.lu.y = a.y;
}else{
while(examine(a.x, a.y+t*2)) t*=2;
ss = a.y+t; ee = a.y+t*2-1;
while(ss<ee){
if(ss==ee-1){
if(examine(a.x, ee)) ss=ee;
else ee=ss;
break;
}
mi=(ss+ee)/2;
if(examine(a.x, mi)) ss = mi;
else ee = mi-1;
}
now.lu.y = ss;
}
a = st; t = 1;
if(!examine(a.x, a.y-1)){
now.rd.y = a.y;
}else{
while(examine(a.x, a.y-t*2)) t*=2;
ss = a.y-t; ee = a.y-t*2+1;
while(ss>ee){
mi=(ss+ee)/2;
if(examine(a.x, mi)) ss = mi;
else ee = mi+1;
}
now.rd.y = ss;
}
a = st; t = 1;
if(!examine(a.x+1, a.y)){
now.rd.x = a.x;
}else{
while(examine(a.x+t*2, a.y)) t*=2;
ss = a.x+t; ee = a.x+t*2-1;
while(ss<ee){
if(ss==ee-1){
if(examine(ee, a.y)) ss=ee;
else ee=ss;
break;
}
mi=(ss+ee)/2;
if(examine(mi, a.y)) ss = mi;
else ee = mi-1;
}
now.rd.x = ss;
}
a = st; t = 1;
if(!examine(a.x-1, a.y)){
now.lu.x = a.x;
}else{
while(examine(a.x-t*2, a.y)) t*=2;
ss = a.x-t; ee = a.x-t*2+1;
while(ss>ee){
mi=(ss+ee)/2;
if(examine(mi, a.y)) ss = mi;
else ee = mi+1;
}
now.lu.x = ss;
}/*
while(1){
if(examine(a.x, a.y+t*2)){
t*=2;
}else{
if(t==1){
if(examine(a.x, a.y+t)) a.y++;
break;
}else{
a.y+=t;
t=1;
}
}
}
now.lu.y = a.y;
a=st; t=1;
while(1){
if(examine(a.x, a.y-t*2)){
t*=2;
}else{
if(t==1){
if(examine(a.x, a.y-t)) a.y--;
break;
}else{
a.y-=t; t=1;
}
}
}
now.rd.y = a.y;
a=st; t=1;
while(1){
if(examine(a.x+t*2, a.y)){
t*=2;
}else{
if(t==1){
if(examine(a.x+t, a.y)) a.x++;
break;
}else{
a.x+=t; t=1;
}
}
}
now.rd.x = a.x;
a=st; t=1;
while(1){
if(examine(a.x-t*2, a.y)){
t*=2;
}else{
if(t==1){
if(examine(a.x-1, a.y)) a.x--;
break;
}else{
a.x-=t;
t=1;
}
}
}
now.lu.x = a.x;
*/
now.cmid();
v[0]=now.mid;
int i=0;
ll M=now.rd.x-now.lu.x+1;
ll dx[4]={M, M, -M, -M}, dy[4]={M, -M, M, -M};
s.insert(make_pair(v[0].x, v[0].y));
while(i<v.size()){
ans.x+=v[i].x; ans.y+=v[i].y;
for(int j=0; j<4; j++){
if(!chk(v[i].x+dx[j], v[i].y+dy[j]) && s.find(make_pair(v[i].x+dx[j], v[i].y+dy[j]))==s.end() && examine(v[i].x+dx[j], v[i].y+dy[j])){
s.insert(make_pair(v[i].x+dx[j], v[i].y+dy[j]));
v.push_back({v[i].x+dx[j], v[i].y+dy[j]});
}
}
i++;
}
printf("solution %lld %lld", ans.x/13, ans.y/13);
fflush(stdout);
}
Compilation message
aliens.cpp: In function 'int main()':
aliens.cpp:179:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<v.size()){
~^~~~~~~~~
aliens.cpp: In function 'bool examine(ll, ll)':
aliens.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", c);
~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld%lld", &N, &st.x, &st.y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
248 KB |
Output is correct |
| 3 |
Correct |
3 ms |
248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
316 KB |
Output is correct |
| 2 |
Correct |
3 ms |
248 KB |
Output is correct |
| 3 |
Correct |
4 ms |
376 KB |
Output is correct |
