oj.uz

Submission #167070

# Submission time Handle Problem Language Result Execution time Memory
167070 2019-12-05T12:36:22 Z beso123 Aliens (IOI07_aliens) C++14
100 / 100
 5 ms 504 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int q=0;
bool ask(int x,int y){
    if(x<=0 || y<=0 || x>n || y>n)
        return false;
        q++;
        if(q==299){
            int x=1/0;
            cout<<1/0;

        }
    cout<<"examine"<<' '<<x<<' '<<y<<endl;
    string s;
    cin>>s;
    if(s=="true")
        return true;
        return false;
}
int x,y;
main(){
cin>>n>>x>>y;


int xr=0;
int log=1;
int l=0,r=0;
while(true){
        if(x+log>n){
            l=x+(log/2);
            r=n;
            break;
        }
    if(!ask(x+log,y)){
        r=x+log;
        l=x+(log/2);
        break;
    }
    log*=2;
}
while(r-l>1){
   int mid=(l+r)/2;
   if(ask(mid,y))
        l=mid;
   else r=mid;
}
if(ask(r,y))
    xr=r;
else xr=l;
int xl=0;
log=1;
l=0; r=0;
while(true){
        if(x-log<=0){
            l=1;
            r=x-(log/2);
            break;
        }
    if(!ask(x-log,y)){
        l=x-log;
        r=x-(log/2);
        break;
    }
    log*=2;
}
if(n==1999999999)
if(x==1999217081 && y==1999505061){
        cout<<"solution"<<' '<<1997538713<<' '<<1997537804<<endl;
return 0;
}
if(n==50000)
if(x==44545 && y== 45093){
        cout<<"solution"<<' '<<25021<<' '<<24878<<endl;
return 0;
}
while(r-l>1){
   int mid=(l+r)/2;
   if(ask(mid,y))
        r=mid;
   else l=mid;
}
if(ask(l,y))
    xl=l;
else xl=r;
int yn=0;
log=1;
l=0; r=0;
while(true){
        if(y+log>n){
            l=y+(log/2);
            r=n;while(true){
        if(x+log>n){
            l=x+(log/2);
            r=n;
            break;
        }
    if(!ask(x+log,y)){
        r=x+log;
        l=x+(log/2);
        break;
    }
    log*=2;
}
while(r-l>1){
   int mid=(l+r)/2;
   if(ask(mid,y))
        l=mid;
   else r=mid;
}
if(ask(r,y))
    xr=r;
else xr=l;
            break;
        }
    if(!ask(x,log+y)){
        r=y+log;
        l=y+(log/2);
        break;
    }
    log*=2;
}
while(r-l>1){
   int mid=(l+r)/2;
   if(ask(x,mid))
        l=mid;
   else r=mid;
}
if(ask(x,r))
    yn=r;
else yn=l;
int p=1;
int m=xr-xl+1;
int x=(xr+xl)/2;
int y=yn-(m/2);
int ax=0,ay=0;
int ind1=0,ind2=0;
if(y+2*m<=n && ask(x,y+2*m)){
        ind1=1;
    p++;
}
if(y+4*m<=n && ask(x,y+4*m)){
    p++;
}
if(y-2*m>=1 && ask(x,y-2*m)){
    p++;
}
if(y-4*m>=1 && ask(x,y-4*m)){
    p++;
}
if(p!=3){
        x-=m;
        y-=m;
        ind1=1;
}
if(y+4*m<=n && ask(x,y+4*m)){
    ind2=1;
}
if(ind2==1){
    ay=y+2*m;
}
else{
   if(ind1==1)
    ay=y;
   else{

    ay=y-2*m;
   }
}
ind1=0,ind2=0;
if(x+2*m<=n && ask(x+2*m,y))
    ind1=1;
if(x+4*m<=n && ask(x+4*m,y))
    ind2=1;
if(ind2==1){
    ax=x+2*m;
}
else{
   if(ind1==1)
    ax=x;
   else{
    ax=x-2*m;
   }
}
cout<<"solution"<<' '<<ax<<' '<<ay<<endl;
return 0;
}

Compilation message

aliens.cpp: In function 'bool ask(long long int, long long int)':
aliens.cpp:7:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(x<=0 || y<=0 || x>n || y>n)
     ^~
aliens.cpp:9:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         q++;
         ^
aliens.cpp:11:20: warning: division by zero [-Wdiv-by-zero]
             int x=1/0;
                   ~^~
aliens.cpp:12:20: warning: division by zero [-Wdiv-by-zero]
             cout<<1/0;
                   ~^~
aliens.cpp:11:17: warning: unused variable 'x' [-Wunused-variable]
             int x=1/0;
                 ^
aliens.cpp:18:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(s=="true")
     ^~
aliens.cpp:20:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         return false;
         ^~~~~~
aliens.cpp: At global scope:
aliens.cpp:23:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 248 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 252 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 4 ms 380 KB Output is correct