oj.uz

Submission #471900

# Submission time Handle Problem Language Result Execution time Memory
471900 2021-09-11T14:48:32 Z JovanB Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 312 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

ll n;

map <pair <ll, ll>, bool> is;

bool ask(ll x, ll y){
    if(x <= 0 || y <= 0 || x > n || y > n) return 0;
    cout << "examine " << x << " " << y << endl;
    string s;
    cin >> s;
    return s == "true";
}

ll sz;

bool check(ll x, ll y){
    for(int i=-2; i<=2; i++){
        for(int j=-2; j<=2; j++){
            if((i+j)%2) continue;
            if(!is[{x + i*sz, y + j*sz}]) return 0;
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    ll x0, y0;
    cin >> n >> x0 >> y0;
    int lm;
    for(lm=0; ; lm++){
        if(!ask(x0 + (1LL << lm), y0)) break;
    }
    ll l = x0 + 1, r = x0 + (1LL << lm) - 1, x2 = x0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(ask(mid, y0)){
            l = mid + 1;
            x2 = mid;
        }
        else r = mid - 1;
    }
    for(lm=0; ; lm++){
        if(!ask(x0 - (1LL << lm), y0)) break;
    }
    l = x0 - (1LL << lm) + 1, r = x0 - 1;
    ll x1 = x0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(ask(mid, y0)){
            r = mid - 1;
            x1 = mid;
        }
        else l = mid + 1;
    }
    sz = x2 - x1 + 1;
    ll xc = (x1+x2)/2;
    for(lm=0; ; lm++){
        if(!ask(x0, y0 + (1LL << lm))) break;
    }
    l = y0 + 1, r = y0 + (1LL << lm) - 1;
    ll y2 = y0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(ask(x0, mid)){
            l = mid + 1;
            y2 = mid;
        }
        else r = mid - 1;
    }
    ll y1 = y2 - sz + 1;
    ll yc = (y1+y2)/2;
    for(int i=-4; i<=4; i++){
        for(int j=-4; j<=4; j++){
            if((i+j)%2) continue;
            ll xn = xc + sz*i;
            ll yn = yc + sz*j;
            is[{xn, yn}] = ask(xn, yn);
        }
    }
    for(int i=-2; i<=2; i++){
        for(int j=-2; j<=2; j++){
            if((i+j)%2) continue;
            if(check(xc + i*sz, yc + j*sz)){
                cout << "solution " << xc + i*sz << " " << yc + j*sz << endl;
                return 0;
            }
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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