제출 #158364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158364		brcode	Aliens (IOI07_aliens)	C++14	100 / 100	4 ms	508 KiB

aliens

#include <iostream>
#include <map>

using namespace std;
map<pair<long long,long long>,long long> m1;
long long n;
bool query(long long a,long long b){
    if(a<=0||b<=0||a>n||b>n){
        return false;
    }
    if(m1[make_pair(a,b)]){
        if(m1[make_pair(a,b)] == 1){
            return true;
        }
        return false;
    }
    cout<<"examine "<<a<<" "<<b<<endl;
    cout.flush();
    string x;
    cin>>x;
    bool res;
    if(x == "true"){
        res = true;
        m1[make_pair(a,b)] = 1;
    }else{
        res = false;
        m1[make_pair(a,b)] = -1;
    }

    m1[make_pair(a,b)] = res;
    return res;
}
long long lb,rb;
int main(){
    long long a,b;
    cin>>n>>a>>b;
    long long curr = a;
    for(long long i=0;i<=31;i++){
        curr-=(1LL<<i);
        if(curr<=0){
            lb = 1;
            rb = (curr+(1LL<<i));
            break;
        }
        if(query(curr,b)){
            continue;
        }else{

            lb = curr;
            rb = curr+(1LL<<i);
            break;
        }
    }

    long long l = lb;
    long long r =rb;
    long long templ =0;
    while(l<=r){
        long long mid = (l+r)/2;
        if(query(mid,b)){
            r=mid-1;
            templ = mid;
        }else{
            l = mid+1;
        }
    }
    curr = a;
    for(long long i=0;i<=31;i++){
        curr+=(1LL<<i);
        if(curr>n){
            lb = curr-(1LL<<i);
            rb = n;
            break;
        }
        if(query(curr,b)){
            continue;
        }else{
            lb = curr-(1LL<<i);
            rb = curr;
            break;
        }
    }
    l = lb;
    r =rb;
    long long tempr =0;
    while(l<=r){
        long long mid = (l+r)/2;
        if(query(mid,b)){
            l=mid+1;
            tempr = mid;
        }else{
            r=mid-1;
        }
    }
    long long m = (tempr-templ+1);
   // cout<<"m :"<<m<<endl;
    curr = b;
    for(long long i=0;i<=31;i++){
        curr+=(1LL<<i);
        if(curr>n){
            lb = curr-(1LL<<i);
            rb = n;
            break;
        }
        if(query(a,curr)){
            continue;
        }else{
            lb = curr-(1LL<<i);
            rb = curr;
            break;
        }
    }
    l = lb;
    r =rb;
    long long tempu =0;
    while(l<=r){
        long long mid = (l+r)/2;
        if(query(a,mid)){
            l=mid+1;
            tempu = mid;
        }else{
            r=mid-1;
        }
    }
    long long tempd = tempu-m+1;
    long long x1 = templ-(2LL*m);
    long long y1 = tempu;


    while(query(x1,y1)){

        x1-=(2LL*m);

    }
    x1+=(2LL*m);
    y1+=(2LL*m);
    while(query(x1,y1)){

        y1+=(2LL*m);

    }
    y1-=(2LL*m);
    if(query(x1-m,y1+m)){
        x1-=m;
        y1+=m;
    }
    x1+=(2LL*m);
    y1-=(2LL*m);
    x1+=(m/2);
    y1-=(m/2);
    cout<<"solution "<<x1<<" "<<y1<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'int main()':
aliens.cpp:125:15: warning: unused variable 'tempd' [-Wunused-variable]
     long long tempd = tempu-m+1;
               ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10