oj.uz

Submission #521655

# Submission time Handle Problem Language Result Execution time Memory
521655 2022-02-02T17:15:13 Z perchuts Aliens (IOI07_aliens) C++17
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

bool query(ll x,ll y){
    cout<<"examine "<<x<<" "<<y<<endl;
    string s;cin>>s;
    return s=="true";
}

int main(){_
    ll n,x0,y0;cin>>n>>x0>>y0;
    //find rightmost, leftmost and topmost coordinates using binsearch
    query(x0,y0);
    ll l,r,leftmost = x0,rightmost = x0,topmost = y0;
    //leftmost
    while(true){
        bool ok = false;
        l = 1, r = leftmost-1LL;
        while(l<=r){
        ll md = l + (r-l+1LL)/2;
        if(query(md,y0)){
            leftmost = md;
            r = md-1LL;
            ok = true;
        }else{
            l = md+1LL;
        }   
    }
        if(!ok)break;
    }
    //rightmost
    while(true){
        bool ok = false;
        l = rightmost + 1LL, r = n;
        while(l<=r){
            ll md = l + (r-l+1LL)/2;
            if(query(md,y0)){
                rightmost = md;
                l = md+1LL;
                ok = true;
            }else{
                r = md-1LL;
            }
        }
        if(!ok)break;        
    }
    //topmost
    l = 1LL, r = y0;
    while(true){
        l = topmost+1, r = n;
        bool ok = false;
        while(l<=r){
        ll md = l + (r-l+1)/2;
        if(query(x0,md)){
            topmost = md;
            l = md+1;
            ok = true;
        }else{
            r = md-1;
        }
        }
        if(!ok)break;
    }

    ll len = rightmost - leftmost + 1;
    ll xc = leftmost + len/2, yc = topmost - len/2;
    cout<<"solution "<<xc<<" "<<yc<<endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 204 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -