oj.uz

Submission #500320

# Submission time Handle Problem Language Result Execution time Memory
500320 2021-12-30T17:25:00 Z gg123_pe Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 288 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
typedef pair <pair<char,char>, pair<char,char>> T; 
#define f(i,a,b) for(ll i = a; i < b; i++)


ll n, x, y, l; 

bool ask(ll a, ll b){
    cout << "examine " << a << " " << b << endl; 
    string s; cin >> s; 
    fflush(stdout);
    return (s == "true" ? 1 : 0);
}
int main(){
    cin >> n >> x >> y; 
    ll up, down, left, right; 

    // up 
    ll ini = y, fin = n; 
    f(i,0,32){
        ll l = x, r = y+(1LL<<i); 
        if(r <= n){
           if(!ask(l,r)) {
               fin = r; 
               break; 
           }
           ini = r; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin+1)>>1; 
        if(ask(x,m)) ini = m;
        else fin = m-1; 
    }
    up = ini; 
    // right 
    ini = x, fin = n; 
    f(i,0,32){
        ll l = x + (1LL<<i), r = y; 
        if(l <= n){
           if(!ask(l,r)) {
               fin = l; 
               break; 
            }
            ini = l; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin+1)>>1; 
        if(ask(m,y)) ini = m;
        else fin = m-1; 
    }
    right = ini;
    // left 
    ini = 1, fin = x; 
    f(i,0,32){
        ll l = x - (1LL<<i), r = y; 
        if(l >= 1){
           if(!ask(l,r)) {
               ini = l; 
               break; 
            }
            fin = l; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin)>>1; 
        if(ask(m,y)) fin = m;
        else ini = m+1; 
    }
    left = ini;
    // down 
    ini = 1, fin = y; 
    f(i,0,32){
        ll l = x, r = y - (1LL<<i); 
        if(r >= 1){
           if(!ask(l,r)) {
               ini = r; 
               break; 
            }
            fin = r; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin)>>1; 
        if(ask(x,m)) fin = m;
        else ini = m+1; 
    }
    down = ini;

    x = (left+right)/2, y = (up+down)/2, l = (up-down+1); 

    vector <pair<ll,ll>> centers; 
    for(ll i = x-4*l; i <= x+4*l; i += 2*l){
        for(ll j = y-4*l; j <= y+4*l; j += 2*l){
            if(i >= 1 and i <= n and j <= n and j >= 1){
                if(ask(i,j)) centers.push_back({i,j});
            }
        }
    }
    x += l, y += l; 
    for(ll i = x-4*l; i <= x+4*l; i += 2*l){
        for(ll j = y-4*l; j <= y+4*l; j += 2*l){
            if(i >= 1 and i <= n and j <= n and j >= 1){
                if(ask(i,j)) centers.push_back({i,j});
            }
        }
    }
    sort(centers.begin(), centers.end()); 
    cout << "solution " << centers[6].first << " " << centers[6].second << endl; 
    fflush(stdout); 
    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 280 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 284 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 264 KB Output is correct

Subtask #4
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 #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 288 KB Output is correct

Subtask #8
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
3 Correct 3 ms 200 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
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
3 Correct 3 ms 284 KB Output is correct