oj.uz

Submission #577086

# Submission time Handle Problem Language Result Execution time Memory
577086 2022-06-14T04:03:48 Z tranxuanbach Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 344 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

int n;

map <pii, bool> mppquery;

bool query(int x, int y){
    if (mppquery.count(make_pair(x, y))){
        return mppquery[make_pair(x, y)];
    }
    if (1 <= x and x <= n and 1 <= y and y <= n){
        cout << "examine " << x << ' ' << y << endl;
        string s; cin >> s;
        if (s == "true"){
            return (mppquery[make_pair(x, y)] = 1);
        }
        else{
            return (mppquery[make_pair(x, y)] = 0);
        }
    }
    else{
        return 0;
    }
}

void answer(int x, int y){
    cout << "solution " << x << ' ' << y << endl;
    exit(0);
}

int sx, sy;

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

int dist[4];
int m;

bool large[9][9];
int ansx, ansy;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> sx >> sy;

    For(d, 0, 4){
        int l = 0, r = 1;
        while (query(sx + dx[d] * r, sy + dy[d] * r)){
            r = r * 2 + 1;
        }
        r--;
        while (l < r){
            int mid = (l + r + 1) >> 1;
            if (query(sx + dx[d] * mid, sy + dy[d] * mid)){
                l = mid;
            }
            else{
                r = mid - 1;
            }
        }
        dist[d] = l;
    }
    m = dist[0] + dist[3] + 1;

    sx = ((sx - dist[0]) + (sx + dist[3])) / 2;
    sy = ((sy - dist[1]) + (sy + dist[2])) / 2;
    For(x, 0, 9){
        For(y, 0, 9){
            if (((x - 4) + (y - 4)) % 2 != 0){
                continue;
            }
            large[x][y] = query(sx + (x - 4) * m, sy + (y - 4) * m);
        }
    }
    For(x, 0, 9){
        For(y, 0, 9){
            if (((x - 4) + (y - 4)) % 2 != 0){
                continue;
            }
            bool ans = 1;
            ForE(dx, -2, 2){
                ForE(dy, -2, 2){
                    if ((dx + dy) % 2 != 0){
                        continue;
                    }
                    if (x + dx < 0 or x + dx >= 9 or y + dy < 0 or y + dy >= 9){
                        ans = 0;
                        break;
                    }
                    ans &= large[x + dx][y + dy];
                }
            }
            if (ans){
                answer(sx + (x - 4) * m, sy + (y - 4) * m);
            }
        }
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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