| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79222 |
2018-10-12T03:04:52 Z |
Plurm |
Aliens (IOI07_aliens) |
C++11 |
|
3 ms |
592 KB |
#include <bits/stdc++.h>
using namespace std;
enum dir{
up, down, lleft, rright
};
int n;
const pair<int,int> NOPE = make_pair(-1,-1);
map<pair<long long,long long>,bool> mp;
bool query(long long x,long long y){
if(x <= 0 || y <= 0 || x > n || y > n) return false;
if(mp.find(make_pair(x,y)) != mp.end()) return mp[make_pair(x,y)];
printf("examine %lld %lld\n",x,y);
fflush(stdout);
char in[8];
scanf("%s",in);
mp[make_pair(x,y)] = in[0] == 't';
return in[0] == 't';
}
pair<int,int> search(long long x,long long y,dir d){
int sstate = 0;
if(d == up){
for(long long i = 1; y+i <= (long long)n; i *= 2ll){
if(query(x,y+i)){
if(sstate == 1){
return make_pair(x,y+i);
}
}else{
if(sstate == 0) sstate = 1;
}
}
return NOPE;
}else if(d == down){
for(long long i = 1; y-i > 0ll; i *= 2ll){
if(query(x,y-i)){
if(sstate == 1){
return make_pair(x,y-i);
}
}else{
if(sstate == 0) sstate = 1;
}
}
return NOPE;
}else if(d == lleft){
for(long long i = 1; x-i > 0ll; i *= 2ll){
if(query(x-i,y)){
if(sstate == 1){
return make_pair(x-i,y);
}
}else{
if(sstate == 0) sstate = 1;
}
}
return NOPE;
}else{
for(long long i = 1; x+i <= (long long)n; i *= 2ll){
if(query(x+i,y)){
if(sstate == 1){
return make_pair(x+i,y);
}
}else{
if(sstate == 0) sstate = 1;
}
}
return NOPE;
}
}
int getsidelength(long long x,long long y){
int byu = -1;
int byd = -1;
for(long long i = 1; ; i *= 2ll){
if(!query(x,y+i)){
int hi = min(i,n-y);
int lo = 0;
int mid;
while(lo < hi){
mid = (lo + hi)/2;
if(query(x,y+mid)){
lo = mid+1;
}else{
hi = mid;
}
}
byu = y+lo;
break;
}
}
for(long long i = 1; ; i *= 2ll){
if(!query(x,y-i)){
int hi = min(i,y);
int lo = 0;
int mid;
while(lo < hi){
mid = (lo + hi)/2;
if(query(x,y-mid)){
lo = mid+1;
}else{
hi = mid;
}
}
byd = y-lo;
break;
}
}
return byu - byd - 1;
}
int main(){
scanf("%d",&n);
int x0,y0;
scanf("%d%d",&x0,&y0);
int m = getsidelength(x0,y0);
auto v0 = search(x0,y0,up);
auto v1 = search(x0,y0,down);
auto v2 = search(x0,y0,lleft);
auto v3 = search(x0,y0,rright);
int mask = 0;
if(v0 != NOPE) mask++;
mask *= 2;
if(v1 != NOPE) mask++;
mask *= 2;
if(v2 != NOPE) mask++;
mask *= 2;
if(v3 != NOPE) mask++;
pair<int,int> nxt;
switch(mask){
case 5:
nxt = search(v1.first,v1.second,down);
if(nxt == NOPE){
nxt.first += m;
nxt.second -= m;
}else{
nxt.first = v1.first + 2*m;
nxt.second = v1.second;
}
break;
case 6:
nxt = search(v1.first,v1.second,down);
if(nxt == NOPE){
nxt.first -= m;
nxt.second -= m;
}else{
nxt.first = v1.first - 2*m;
nxt.second = v1.second;
}
break;
case 7:
nxt = v1;
break;
case 9:
nxt = search(v0.first,v0.second,up);
if(nxt == NOPE){
nxt.first += m;
nxt.second += m;
}else{
nxt.first = v0.first + 2*m;
nxt.second = v0.second;
}
break;
case 10:
nxt = search(v0.first,v0.second,up);
if(nxt == NOPE){
nxt.first -= m;
nxt.second += m;
}else{
nxt.first = v0.first - 2*m;
nxt.second = v0.second;
}
break;
case 11:
nxt = v0;
break;
case 13:
nxt = v3;
break;
case 14:
nxt = v2;
break;
case 15:
nxt = make_pair(x0,y0);
break;
}
int x = nxt.first;
int y = nxt.second;
int lo = 0;
int hi = m+1;
int mid;
int byu = 0;
int byd = 0;
int bxl = 0;
int bxr = 0;
while(lo < hi){
mid = (lo + hi)/2;
if(query(x,y+mid)){
lo = mid+1;
}else{
hi = mid;
}
}
byu = y+lo;
lo = 0;
hi = m+1;
while(lo < hi){
mid = (lo + hi)/2;
if(query(x,y-mid)){
lo = mid+1;
}else{
hi = mid;
}
}
byd = y-lo;
lo = 0;
hi = m+1;
while(lo < hi){
mid = (lo + hi)/2;
if(query(x-mid,y)){
lo = mid+1;
}else{
hi = mid;
}
}
bxl = x-lo;
lo = 0;
hi = m+1;
while(lo < hi){
mid = (lo + hi)/2;
if(query(x+mid,y)){
lo = mid+1;
}else{
hi = mid;
}
}
bxr = x+lo;
printf("solution %d %d\n",(bxl + bxr)/2,(byd + byu)/2);
return 0;
}
Compilation message
aliens.cpp: In function 'bool query(long long int, long long int)':
aliens.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",in);
~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aliens.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x0,&y0);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
360 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
408 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
592 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
592 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
592 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
592 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
592 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
592 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
