oj.uz

Submission #347119

# Submission time Handle Problem Language Result Execution time Memory
347119 2021-01-11T21:31:58 Z jDO_ Aliens (IOI07_aliens) C++14
100 / 100
 2 ms 384 KB 
// #include"alienslib.h"
#include<bits/stdc++.h>
using namespace std;
int examine(int X, int Y){
    string a;
    cout << "examine " << X << ' ' << Y << '\n' << flush;
    cin >> a;
    if(a == "true") return 1;
    else            return 0;
}
void solution(int X, int Y){
    cout << "solution " << X << ' ' << Y << '\n' << flush;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x, y;
    string a;
    cin >> n >> x >> y;
    // get_size_and_start(int &n, int &x, int &y);
    long long l = 0, r = 0, b1, b2;
    b1 = x, b2 = n;
    while(b1 != b2){
        int mid = (b1+b2+1)/2;
        if(examine(mid, y)) b1 = mid;
        else                b2 = mid-1;
    }
    r = b1;
    b1 = 1, b2 = x;
    while(b1 != b2){
        int mid = (b1+b2)/2;
        if(examine(mid, y)) b2 = mid;
        else            b1 = mid+1;
    }
    l = b1;
    if(!examine((l+r)/2, y))    r = (r+2*l-2)/3;
    else{        
        if(!examine(l+((r-l+1)*3/10), y))    r = (r+4*l-4)/5;
    }
    int m = r-l+1;
    // cout << m << endl;
    b1 = max(1, y-m+1), b2 = y;
    while(b1 != b2){
        int mid = (b1+b2)/2;        
        if(examine(x, mid)) b2 = mid;
        else            b1 = mid+1;
    }
    long long cx = (r+l)/2, cy = b1 + m/2;
    if(cx + m <= n && cy + m <= n){       
        if(!examine(cx + m, cy + m)){
            cx -= m;
            cy -= m;
        }
    }
    else{
        cx -= m;
        cy -= m;
    }
    if(cx + m <= n && cy - m >= 1){        
        if(!examine(cx + m, cy - m)){
            cx -= m;
            cy += m;
        }
    }
    else{
        cx -= m;
        cy += m;
    }
    if(cx - m >= 1 && cy + m <= n){        
        if(!examine(cx - m, cy + m)){
            cx += m;
            cy -= m;
        }
    }
    else{
        cx += m;
        cy -= m;
    }
    if(cx - m >= 1 && cy - m >= 1){        
        if(!examine(cx - m, cy - m)){
            cx += m;
            cy += m;
        }
    }
    else{
        cx += m;
        cy += m;
    }
    int xx = 0, yy = 0;
    if(cx - 2*m >= 1 && cy - 2*m >= 1){       
        if(examine(cx - 2*m, cy - 2*m)){
            xx -= m;
            yy -= m;
        }
    }
    if(cx + 2*m <= n && cy - 2*m >= 1){        
        if(examine(cx + 2*m, cy - 2*m)){
            xx += m;
            yy -= m;
        }
    }
    if(cx - 2*m >= 1 && cy + 2*m <= n){       
        if(examine(cx - 2*m, cy + 2*m)){
            xx -= m;
            yy += m;
        }
    }
    if(cx + 2*m >= 1 && cy + 2*m >= 1){        
        if(examine(cx + 2*m, cy + 2*m)){
            xx += m;
            yy += m;
        }
    }
    solution(cx + xx, cy + yy);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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