oj.uz

Submission #158364

# Submission time Handle Problem Language Result Execution time Memory
158364 2019-10-16T18:05:47 Z brcode Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 508 KB 
#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;
}

Compilation message

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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