oj.uz

Submission #862345

# Submission time Handle Problem Language Result Execution time Memory
862345 2023-10-18T05:14:45 Z HuyQuang_re_Zero Aliens (IOI07_aliens) C++14
100 / 100
 1 ms 356 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
ll n,x,y,xmx,xmn,ymx,ymn,len,xl,xr,yr,l,r,M;
struct Interactive
{
    int a[105][105],n,m,x0,y0,i,j;
    void Init(int _n,int _m,int _x0,int _y0)
    {
        n=_n; m=_m; x0=_x0; y0=_y0;
        for(i=x0;i<=x0+5*m-1;i++)
            for(j=y0;j<=y0+5*m-1;j++)
            {
                int x=i-x0,y=j-y0;
                if((x/m+y/m)%2==0) a[i][j]=1;
            }
    }
    void debug()
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++) cout<<a[i][j]<<" ";
            cout<<'\n';
        }
    }
} IR;
int ask(int x,int y)
{
    cout<<"examine "<<x<<" "<<y<<'\n';
  //  return IR.a[x][y];
    string s;
    cin>>s;
    return (s=="true");
}
int main()
{
  //  freopen("aliens.inp","r",stdin);
    //freopen("aliens.out","w",stdout);
    ll x0,y0;
    cin>>n>>x0>>y0;
   // IR.Init(19,3,5,2);
    //IR.debug();
    for(len=1;len<=30;len++)
    {
        ll x=x0+(1<<len)-1;
        if(x>n || ask(x,y0)==0) break;
    }
    len--;
    x=x0+(1<<len)-1;
    l=x,r=min(n,x+(1<<len));
    while(l<r)
    {
        ll mid=(l+r+1)>>1;
        if(ask(mid,y0)) l=mid; else r=mid-1;
    }
    xr=l;


    for(len=1;len<=30;len++)
    {
        ll x=x0-(1<<len)+1;
        if(x<1 || ask(x,y0)==0) break;
    }
    len--;
    x=x0-(1<<len)+1;
    l=max(1LL,x-(1<<len)),r=x;
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(ask(mid,y0)) r=mid; else l=mid+1;
    }
    xl=l;
    M=xr-xl+1;

    for(len=1;len<=30;len++)
    {
        ll y=y0+(1<<len)-1;
        if(y>n || ask(x0,y)==0) break;
    }
    len--;
    y=y0+(1<<len)-1;
    l=y,r=min(n,y+(1<<len));
    while(l<r)
    {
        ll mid=(l+r+1)>>1;
        if(ask(x0,mid)) l=mid; else r=mid-1;
    }
    yr=l;

    for(xmn=xr;xmn>=1;xmn-=2*M)
        if(ask(xmn,yr)==0) break;
    xmn=xmn+2*M-M+1;

    for(xmx=xr;xmx<=n;xmx+=2*M)
        if(ask(xmx,yr)==0) break;
    xmx=xmx-2*M;

    for(ymn=yr;ymn>=1;ymn-=2*M)
        if(ask(xr,ymn)==0) break;
    ymn=ymn+2*M-M+1;

    for(ymx=yr;ymx<=n;ymx+=2*M)
        if(ask(xr,ymx)==0) break;
    ymx=ymx-2*M;
    cout<<"solution "<<(xmn+xmx)/2<<" "<<(ymn+ymx)/2;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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