oj.uz

Submission #100697

# Submission time Handle Problem Language Result Execution time Memory
100697 2019-03-13T12:13:39 Z muradeyn Aliens (IOI07_aliens) C++14
80 / 100
 3 ms 424 KB 
/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second

using namespace std;

intt n;

string s;

map< pair<intt,intt> ,intt >mp;

bool ask(intt x,intt y) {
    if (mp[{x,y}])return mp[{x,y}] == 1;
    if (x >= n || x < 1 || y >= n || y < 1)return false;
    cout<<"examine "<<x<<" "<<y<<endl;
    cin>>s;
    if (s == "true")mp[{x,y}] = 1;
    else mp[{x,y}] = 2;
    return (s == "true");
}

bool pos(intt x,intt y) {
    if (x >= n || x < 1 || y >= n || y < 1)return false;
    return true;
}

intt x , y , old , rgx , lfx , m , pw , dwy , upy;

int main()
{
    FAST_READ;
    cin>>n>>x>>y;
    //Right most
    old = x; rgx = x; pw = 1;
    while (ask(x + pw , y)) {
        old = x + pw;
        pw *= 2;
    }
    intt l = old , r = x + pw;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ask(mid , y)) {
            rgx = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    old = x; lfx = x; pw = 1;
    while (ask(x - pw , y)) {
        old = x - pw;
        pw *= 2;
    }
    l = x - pw; r = old;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ask(mid , y)) {
            r = mid - 1;
            lfx = mid;
        }
        else l = mid + 1;
    }
    m = rgx - lfx + 1;
    old = y; dwy = y; pw = 1;
    while (ask(x,y + pw)) {
        old = y + pw;
        pw *= 2;
    }
    l = old; r = y + pw;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ask(x,mid)) {
            l = mid + 1;
            dwy = mid;
        }
        else r = mid - 1;
    }
    upy = dwy - m + 1;
    //cout<<lfx<<" "<<rgx<<endl;
    //cout<<upy<<" "<<dwy<<endl;
    //cout<<m<<endl;
    x = lfx + (rgx - lfx) / 2;
    y = upy + (dwy - upy) / 2;
    if (ask(x + 4 * m,y)) x += 2 * m;
    else if (!(ask(x + 2 * m,y) && ask(x - 2 * m,y))) {
        if (ask(x - 4 * m,y))x -= 2 * m;
        else if (ask(x + 2 * m,y)) x += m , y += m;
        else x -= m , y += m;
    }
    if (ask(x,y + 4 * m)) y += 2 * m;
    else if (!(ask(x,y + 2 * m) && ask(x , y - 2 * m))) {
        if (ask(x,y - 4 * m))y -= 2 * m;
        else if (ask(x,y + 2 * m)) x += m , y += m;
        else x += m , y -= m;
    }
    cout<<"solution "<<x<<" "<<y<<endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 424 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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