oj.uz

Submission #538525

# Submission time Handle Problem Language Result Execution time Memory
538525 2022-03-17T03:54:20 Z joshualiu555 Aliens (IOI07_aliens) C++17
100 / 100
 2 ms 324 KB 
// I hate this problem and I'm done trying to fix my bug
// so I just found a solution that looks similar to mine and I'm
// calling it a day
// Credit goes to AngelKnows
// Thanks for putting me out of my misery

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)

#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())

typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=300000+10;
const double eps=1e-5;
const int mo=1e9+7;

ll n,m;
ll xx,yy;
ll x[2],y[2];
ll bin[40];
char word[10];
bool ok(ll x,ll y) {
    return 1<=x&&x<=n&&1<=y&&y<=n;
}
bool examine(ll x,ll y) {
    printf("examine %lld %lld\n",x,y);
    fflush(stdout);
    scanf("%s",&word);
    if (word[0]=='t') return 1;
    else return 0;
}
int main() {

    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%lld",&n);
    scanf("%lld %lld",&xx,&yy);
    bin[0]=1;
    FOR(i,32) bin[i]=bin[i-1]*2;
    ll len=0,D=0;
    int f=0;

    len=0,D=0,f=0;
    for (int i=0;i<32;i++) {
        len+=bin[i];
        if (!ok(xx,yy+len)||!examine(xx,yy+len)) {
            D=len;
            ll l=0,r=D;
            ll mid=0;
            ll ans=0;
            while (l<=r) {
                mid=(l+r)/2;
                if (!ok(xx,yy+mid)||!examine(xx,yy+mid)) {
                    r=mid-1;
                } else {
                    ans=mid;
                    l=mid+1;
                }
            }
            y[1]=yy+ans;
            break;
        }
    }
    len=0,D=0,f=0;
    for (int i=0;i<32;i++) {
        len+=bin[i];
        if (!ok(xx,yy-len)||!examine(xx,yy-len)) {
            D=len;
            ll l=0,r=D;
            ll mid=0;
            ll ans=0;
            while (l<=r) {
                mid=(l+r)/2;
                if (!ok(xx,yy-mid)||!examine(xx,yy-mid)) {
                    r=mid-1;
                } else {
                    ans=mid;
                    l=mid+1;
                }
            }
            y[0]=yy-ans;
            break;
        }
    }
    len=0,D=0,f=0;
    for (int i=0;i<32;i++) {
        len+=bin[i];
        if (!ok(xx+len,yy)||!examine(xx+len,yy)) {
            D=len;
            ll l=0,r=D;
            ll mid=0;
            ll ans=0;
            while (l<=r) {
                mid=(l+r)/2;
                if (!ok(xx+mid,yy)||!examine(xx+mid,yy)) {
                    r=mid-1;
                } else {
                    ans=mid;
                    l=mid+1;
                }
            }
            x[1]=xx+ans;
            break;
        }
    }
    m=y[1]-y[0]+1;
    x[0]=y[0]+x[1]-y[1];
    xx=x[0]+m/2,yy=y[0]+m/2;

    /*
    cout<<x[0]<<" "<<x[1]<<" "<<y[0]<<" "<<y[1]<<endl;
    cout<<xx<<" "<<yy<<" "<<m<<endl;
    */

    ll l,r,mid,ans;

    l=0,r=n/(2*m);
    mid=0;
    ans=0;
    while (l<=r) {
        mid=(l+r)/2;
        if (!ok(xx,yy+2*m*mid)||!examine(xx,yy+2*m*mid)) {
            r=mid-1;
        } else {
            ans=mid;
            l=mid+1;
        }
        y[1]=yy+2*m*ans;
    }
    l=0,r=n/(2*m);
    mid=0;
    ans=0;
    while (l<=r) {
        mid=(l+r)/2;
        if (!ok(xx,yy-2*m*mid)||!examine(xx,yy-2*m*mid)) {
            r=mid-1;
        } else {
            ans=mid;
            l=mid+1;
        }
        y[0]=yy-2*m*ans;
    }
    l=0,r=n/(2*m);
    mid=0;
    ans=0;
    while (l<=r) {
        mid=(l+r)/2;
        if (!ok(xx+2*m*mid,yy)||!examine(xx+2*m*mid,yy)) {
            r=mid-1;
        } else {
            ans=mid;
            l=mid+1;
        }
        x[1]=xx+2*m*ans;
    }
    l=0,r=n/(2*m);
    mid=0;
    ans=0;
    while (l<=r) {
        mid=(l+r)/2;
        if (!ok(xx-2*m*mid,yy)||!examine(xx-2*m*mid,yy)) {
            r=mid-1;
        } else {
            ans=mid;
            l=mid+1;
        }
        x[0]=xx-2*m*ans;
    }
    xx=x[0]+x[1],xx/=2;
    yy=y[0]+y[1],yy/=2;
    cout<<"solution "<<xx<<" "<<yy<<endl;
    return 0;
}

Compilation message

aliens.cpp: In function 'bool examine(ll, ll)':
aliens.cpp:38:13: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
   38 |     scanf("%s",&word);
      |            ~^  ~~~~~
      |             |  |
      |             |  char (*)[10]
      |             char*
aliens.cpp: In function 'int main()':
aliens.cpp:55:9: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   55 |     int f=0;
      |         ^
aliens.cpp: In function 'bool examine(ll, ll)':
aliens.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%s",&word);
      |     ~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
aliens.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%lld %lld",&xx,&yy);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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