| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79226 |
2018-10-12T03:56:47 Z |
Plurm |
Aliens (IOI07_aliens) |
C++11 |
|
3 ms |
628 KB |
#include <bits/stdc++.h>
using namespace std;
enum dir{
up, down, lleft, rright
};
int n;
const pair<long long,long long> 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<long long,long long> 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;
}
}
long long getsidelength(long long x,long long y){
long long byu = -1ll;
long long byd = -1ll;
for(long long i = 1; ; i *= 2ll){
if(!query(x,y+i)){
long long hi = min(i,n-y);
long long lo = 0ll;
long long mid;
while(lo < hi){
mid = (lo + hi)/2ll;
if(query(x,y+mid)){
lo = mid+1ll;
}else{
hi = mid;
}
}
byu = y+lo;
break;
}
}
for(long long i = 1; ; i *= 2ll){
if(!query(x,y-i)){
long long hi = min(i,y);
long long lo = 0ll;
long long mid;
while(lo < hi){
mid = (lo + hi)/2ll;
if(query(x,y-mid)){
lo = mid+1ll;
}else{
hi = mid;
}
}
byd = y-lo;
break;
}
}
return byu - byd - 1ll;
}
int main(){
scanf("%d",&n);
long long x0,y0;
scanf("%lld%lld",&x0,&y0);
long long m = getsidelength(x0,y0);
//printf("%lld\n",m);
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<long long,long long> nxt;
//printf("DBG %d\n",mask);
switch(mask){
case 5:
nxt = search(v1.first,v1.second,down);
if(nxt == NOPE){
nxt.first = x0 + m;
nxt.second = y0 - m;
}else{
nxt.first = v1.first + 2ll*m;
nxt.second = v1.second;
}
break;
case 6:
nxt = search(v1.first,v1.second,down);
if(nxt == NOPE){
nxt.first = x0 - m;
nxt.second = y0 - m;
}else{
nxt.first = v1.first - 2ll*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 = x0 + m;
nxt.second = y0 + m;
}else{
nxt.first = v0.first + 2ll*m;
nxt.second = v0.second;
}
break;
case 10:
nxt = search(v0.first,v0.second,up);
if(nxt == NOPE){
nxt.first = x0 - m;
nxt.second = y0 + m;
}else{
nxt.first = v0.first - 2ll*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;
}
long long x = nxt.first;
long long y = nxt.second;
//printf("DBGDBG %d %d\n",x,y);
long long lo = 0;
long long hi = m+1;
long long mid;
long long byu = 0;
long long byd = 0;
long long bxl = 0;
long long bxr = 0;
while(lo < hi){
mid = (lo + hi)/2ll;
if(query(x,y+mid)){
lo = mid+1ll;
}else{
hi = mid;
}
}
byu = y+lo;
lo = 0ll;
hi = m+1ll;
while(lo < hi){
mid = (lo + hi)/2ll;
if(query(x,y-mid)){
lo = mid+1ll;
}else{
hi = mid;
}
}
byd = y-lo;
lo = 0ll;
hi = m+1ll;
while(lo < hi){
mid = (lo + hi)/2ll;
if(query(x-mid,y)){
lo = mid+1ll;
}else{
hi = mid;
}
}
bxl = x-lo;
lo = 0ll;
hi = m+1ll;
while(lo < hi){
mid = (lo + hi)/2ll;
if(query(x+mid,y)){
lo = mid+1ll;
}else{
hi = mid;
}
}
bxr = x+lo;
printf("solution %lld %lld\n",(bxl + bxr)/2ll,(byd + byu)/2ll);
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("%lld%lld",&x0,&y0);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
456 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
456 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
456 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
456 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
488 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
628 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
628 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
628 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
628 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
