oj.uz

Submission #122132

# Submission time Handle Problem Language Result Execution time Memory
122132 2019-06-27T16:17:49 Z tselmegkh Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;

#define INF 1e9
#define MAX 100005
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define ull long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
#define zai <<' '<<
#define all(a) a.begin(),a.end()
#define pc __builtin_popcount
#define debug(args...)  cerr << #args << " = "; Dbg,args; cerr << nl;
struct Dbg { template<typename T> Dbg& operator,(const T& v) { cerr << v << ", "; return *this; } } Dbg;
template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){
if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;}
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
template<class C> void mini(C &_a, C _b) { _a = min(_a, _b); }
template<class C> void maxi(C &_a, C _b) { _a = max(_a, _b); }

ull n, x, y, rx, lx, bx, by;
bool ask(ull qx, ull qy){
    if(qx < 1 || qy < 1 || qx > n || qy > n)return false;
    cout << "examine " << qx << ' ' << qy << endl;
    string response;
    cin >> response;
    return (response == "true");
}
int main(){
    cin >> n >> x >> y;
    ull b = 1;
    ull tmpx = x,tmpy = y;
    while(ask(tmpx + b, tmpy)){
        tmpx += b;
        b = b << 1;
    }
    ull l = tmpx , r = min(tmpx + b, n);
    while(l != r){
        ull mid = (l + r + 1) >> 1;
        if(ask(mid, tmpy)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    b = 1;
    rx = l;
    //cout << "baruun bulan: " << rx << endl;

    tmpx = x, tmpy = y;
    while(ask(tmpx - b, tmpy)){
        tmpx -= b;
        b = b << 1;
    }
    l = max(1LL,tmpx - b), r = tmpx;
    while(l != r){
        ull mid = (l + r) >> 1;
        if(ask(mid, tmpy)){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    b = 1;
    lx = r;
    //cout << "zuun bulan: " << lx << endl;
    tmpx = x, tmpy = y;
    while(ask(tmpx,tmpy - b)){
        tmpy -= b;
        b = b << 1;
    }
    l = max(1LL,tmpy - b), r = tmpy;
    while(l != r){
        ull mid = (l + r) >> 1;
        if(ask(tmpx, mid)){
            r = mid;
        }
        else l = mid + 1;
    }
    ull boty = r;
    //cout << "bottom bulan: " << boty << endl;
    ull m = (rx - lx) + 1;
    //cout << "m = " << m << endl;
    ull centrey = boty + (m - 1) / 2;
    ull centrex = lx + (m - 1) / 2;

    while(ask(centrex - 2 * m, centrey))centrex -= 2 * m;
    while(ask(centrex - m, centrey - m))centrex -= m, centrey -= m;
    while(ask(centrex, centrey - 2 * m))centrey -= 2 * m;

    cout << "solution " << centrex + 2 * m zai centrey + 2 * m << endl;

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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