제출 #1337134

#제출 시각아이디문제언어결과실행 시간메모리
1337134khanhphucscratchAliens (IOI07_aliens)C++20
80 / 100
1 ms416 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool debug_mode = 0;
int xans, yans, sdans = 0;
int n, a[1005][1005];
int ask(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > n) return 0;
    cout<<"examine "<<x<<" "<<y<<endl;
    if(debug_mode == 1) return a[y][x];
    string ans; cin>>ans;
    return (ans == "true");
}
signed main()
{
    int row, col; cin>>n>>row>>col;
    if(debug_mode == 1){
        cin>>xans>>yans>>sdans;
        for(int i = -2; i <= 2; i++){
            for(int j = -2; j <= 2; j++) if((i+j)%2 == 0){
                for(int k = -sdans/2; k <= sdans/2; k++){
                    for(int l = -sdans/2; l <= sdans/2; l++) a[yans+j*sdans+l][xans+i*sdans+k] = 1;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++) cerr<<a[i][j]<<" ";
            cerr<<endl;
        }
    }
    //Does some binary search (62 queries)
    int l = 1, r = col, lecol = 0;
    while(l <= r){
        int mid = (l+r)/2;
        if(ask(row, mid) == 1){lecol = mid; r = mid-1;}
        else l = mid+1;
    }
    l = col; r = n; int ricol = 0;
    while(l <= r){
        int mid = (l+r)/2;
        if(ask(row, mid) == 1){ricol = mid; l = mid+1;}
        else r = mid-1;
    }
    //Solve some edge case (1 query)
    int len = ricol - lecol + 1, sd = len;
    if(sd%3 == 0){
        //First case: 3 different squares
        int mid = (lecol + ricol)/2;
        if(ask(row, mid) == 0) sd /= 3;
    }
    else if(sd%5 == 0){
        //Second case: 5 different squares
        if(ask(row, lecol + sd/5) == 0) sd /= 5;
    }
    //Now we have sd, need to find the middle square (62 queries)
    l = max(col-sd+1, 1ll); r = min(col+sd-1, n);
    while(l <= r){
        int mid = (l+r)/2;
        if(ask(row, mid) == 1){col = mid; r = mid-1;}
        else l = mid+1;
    }
    col += sd/2;
    l = max(row-sd+1, 1ll); r = min(row+sd-1, n);
    while(l <= r){
        int mid = (l+r)/2;
        if(ask(mid, col) == 1){row = mid; r = mid-1;}
        else l = mid+1;
    }
    row += sd/2;
    //Now, we have a simple algorithm: Go till the lowest square and then back up (at most 8 queries)
    while(col + 2*sd <= n && ask(row, col + 2*sd) == 1) col += 2*sd;
    while(row + 2*sd <= n && ask(row + 2*sd, col) == 1) row += 2*sd;
    while(row+sd <= n && col+sd <= n && ask(row+sd, col+sd) == 1){row += sd; col += sd;}
    row -= 2*sd; col -= 2*sd;
    cout<<"solution "<<row<<" "<<col;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...