oj.uz

답안 #289268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289268 2020-09-02T13:52:56 Z zecookiez Aliens (IOI07_aliens) C++17
0 / 100
 5 ms 532 KB 
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int len(const C&c){return int(c.size());}

const int DX[9] = {-4, -2, 0, 2, 4, -3, -1, 1, 3};
const int DY[41] = {-4, -4, -4, -4, -4, -3, -3, -3, -3, -2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4};

const int DDX[13] = {-2, 0, 2, -1, 1, -2, 0, 2, -1, 1, -2, 0, 2};
const int DDY[13] = {-2, -2, -2, -1, -1, 0, 0, 0, 1, 1, 2, 2, 2};
long long N;

bool rng(long long X){
    return 1 <= X && X <= N;
}

map<pair<long long, long long>, bool> memo;
bool query(long long X, long long Y){
    if(!rng(X) || !rng(Y)) return false;
    if(memo.count(make_pair(X, Y))) return memo[make_pair(X, Y)];
    assert(memo.size() < 300);
    cout << "examine " << X << " " << Y << endl;
    string s; cin >> s;
    return memo[make_pair(X, Y)] = (s == "true");
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long XS, YS, X1, Y1, X2, SZ, XC, YC; cin >> N >> XS >> YS;
    // find offset from center of current square
    X1 = XS; Y1 = YS;
    while(true){
        for(long long i = 1;; i += i){
            if(!query(X1 + i, Y1)){
                X1 += i / 2LL; break;
            }
        }
        if(!query(X1 + 1, Y1)) break;
    }
    X2 = XS;
    while(true){
        for(long long i = 1;; i += i){
            if(!query(X2 - i, Y1)){
                X2 -= i / 2LL; break;
            }
        }
        if(!query(X2 - 1, Y1)) break;
    }
    // stupid
    SZ = X1 - X2 + 1; XC = (X1 + X2) / 2;
    while(true){
        for(long long i = 1;; i += i){
            if(!query(XC, Y1 - i)){
                Y1 -= i / 2LL; break;
            }
        }
        cout << Y1 << endl;
        if(!query(XC, Y1 - 1)) break;
    }
    YC = Y1 + SZ / 2;
    for(int i = 0; i < 41; ++i){
        X1 = XC + SZ * DX[i % 9];
        Y1 = YC + SZ * DY[i];
        if(!rng(X1) || !rng(Y1)) continue;
        int cnt = 0;
        for(int j = 0; j < 13; ++j){
            XS = X1 + SZ * DDX[j];
            YS = Y1 + SZ * DDY[j];
            if(rng(XS) && rng(YS) && query(XS, YS)) ++cnt;
            else break;
        }
        if(cnt == 13){
            cout << "solution " << X1 << " " << Y1 << endl;
            memo.clear();
            return 0;
        }
    }
    memo.clear();
    assert(false);
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -