Submission #338757

# Submission time Handle Problem Language Result Execution time Memory
338757 2020-12-23T20:25:57 Z Ahmad_Hasan Aliens (IOI07_aliens) C++17
20 / 100
5 ms 364 KB
#include <bits/stdc++.h>


using namespace std;

int n,x,y;

bool examn(int xe,int ye){
    if(xe<1||xe>n||ye<1||ye>n)
        return false;
    /**if(abs(xe-x)%6<=1&&abs(ye-y)%6<=1)
            return true;
    return false;*/
    cout<<"examine"<<' '<<xe<<' '<<ye<<'\n';
    fflush(stdout);

    string in;
    cin>>in;
    if(in=="true")
        return true;
    return false;
}

bool examnx(int xb,int yb,int xe){
    if(xe<1)
        return false;
    if(xb>xe){
        int l=xb,r=xe;
        while(examn(r,yb)&&l>r){
            r=l-(r-l)/2;
        }
        if(r>=l)
            return true;
        return false;
    }else{
        int l=xb,r=xe;
        while(examn(r,yb)&&r>l){
            r=(r-l)/2+l;
        }
        if(r<=l)
            return true;
        return false;
    }

}

bool examny(int xb,int yb,int ye){
    if(ye<1)
        return false;
    if(yb>ye){
        int l=yb,r=ye;
        while(examn(xb,r)&&l>r){
            r=l-(r-l)/2;
        }
        if(r>=l)
            return true;
        return false;
    }else{
        int l=yb,r=ye;
        while(examn(xb,r)&&r>l){
            r=(r-l)/2+l;
        }
        if(r<=l)
            return true;
        return false;
    }
}


int main()
{
    cin>>n>>x>>y;

    int l=0,r=1e9;
    int ux,lx,ly,ry;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examnx(x,y,x+mid)){
            ux=x+mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    l=0,r=1e9;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examnx(x,y,x-mid)){
            lx=x-mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    l=0,r=1e9;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examny(x,y,y+mid)){
            ry=y+mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    l=0,r=1e9;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examny(x,y,y-mid)){
            ly=y-mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    int h=0,w=0;
    l=0,r=1e9;
    int up=0;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examn(x,ry+2*(ry-ly+1)*mid)){
            l=mid+1;
            up=ry+2*(ry-ly+1)*mid;
        }else{
            r=mid-1;
        }
    }
    l=0,r=1e9;
    int dn=0;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examn(x,ly-2*(ry-ly+1)*mid)){
            l=mid+1;
            dn=ly-2*(ry-ly+1)*mid;
        }else{
            r=mid-1;
        }
    }
    l=0,r=1e9;
    int rt=0;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examn(ux+2*(ry-ly+1)*mid,y)){
            l=mid+1;
            rt=ux+2*(ry-ly+1)*mid;
        }else{
            r=mid-1;
        }
    }
    l=0,r=1e9;
    int lf=0;
    while(l<=r){
        int mid=(r-l)/2+l;
        if(examn(lx-2*(ry-ly+1)*mid,y)){
            l=mid+1;
            lf=lx-2*(ry-ly+1)*mid;
        }else{
            r=mid-1;
        }
    }

    cout<<"solution "<<(rt-lf)/2+lf<<' '<<(up-dn)/2+dn;
    fflush(stdout);

    return 0;
}
/****

1
8 4
3 1
4 3
1 8
8 7

1
100 9
1 100
2 1
3 2
4 3
5 4
100 99
99 98
98 97
97 96

*/

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:115:9: warning: unused variable 'h' [-Wunused-variable]
  115 |     int h=0,w=0;
      |         ^
aliens.cpp:115:13: warning: unused variable 'w' [-Wunused-variable]
  115 |     int h=0,w=0;
      |             ^
aliens.cpp:131:17: warning: 'ly' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |         if(examn(x,ly-2*(ry-ly+1)*mid)){
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:120:17: warning: 'ry' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |         if(examn(x,ry+2*(ry-ly+1)*mid)){
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:153:17: warning: 'lx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |         if(examn(lx-2*(ry-ly+1)*mid,y)){
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:142:17: warning: 'ux' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |         if(examn(ux+2*(ry-ly+1)*mid,y)){
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Incorrect
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Incorrect
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 4 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Runtime error 5 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -