oj.uz

Submission #122556

# Submission time Handle Problem Language Result Execution time Memory
122556 2019-06-28T15:25:35 Z Osama_Alkhodairy Aliens (IOI07_aliens) C++17
10 / 100
 1000 ms 560 KB 
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, x, y;
//~ int X, Y, M, grid[1001][1001];
map <pair <int, int>, int> mp;
int asked = 300;

bool ask(int row, int col){
    if(row < 1 || row > n || col < 1 || col > n) return 0;
    if(mp.find({row, col}) != mp.end()) return mp[{row, col}];
    asked--;
    assert(asked >= 0);
    cout << "examine " << row << " " << col << endl;
    string ret;
    cin >> ret;
    return (mp[{row, col}] = ret[0] == 't');
    //~ return (mp[{row, col}] = grid[row][col]);
}
void answer(int row, int col){
    //~ assert(row == X + 2 * M + M / 2);
    //~ assert(col == Y + 2 * M + M / 2);   
    cout << "solution " << row << " " << col << endl;
}
int findup(int row, int col){
    int l = 1, r = row;
    while(l <= r){
        int mid = (l + r) / 2;
        if(ask(mid, col)) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int findleft(int row, int col){
    int l = 1, r = col;
    while(l <= r){
        int mid = (l + r) / 2;
        if(ask(row, mid)) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int finddown(int row, int col){
    int l = row, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(ask(mid, col)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
int check(int m, int x, int y){
    if(m == 1) return 0;
    if(m % 2 == 0) return 0;
    int ret = 0;
    for(int i = -5 ; i <= 5 ; i++){
        for(int j = -5 ; j <= 5 ; j++){
            if((i + j) % 2) continue;
            if(ask(x + i * m, y + j * m) == 0) continue;
            ret++;
            if(ask(x + i * m - 1, y + j * m) || ask(x + i * m, y + j * m - 1)) return 0;
            if(ret > 13) return 0;
        }
    }
    return ret == 13;
}
//~ int color(int row, int col){
    //~ assert(1 <= row && row <= n);
    //~ assert(1 <= col && col <= n);
    //~ int l = row - X;
    //~ int r = col - Y;
    //~ if(l < 0 || r < 0) return 0;
    //~ if(l >= 5 * M || r >= 5 * M) return 0;
    //~ l %= 2 * M;
    //~ r %= 2 * M;
    //~ if(l < M && r < M) return 1;
    //~ if(l < M) return 0;
    //~ if(r < M) return 0;
    //~ return 1;
//~ }
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> x >> y;
    //~ cin >> X >> Y >> M;
    //~ for(int i = 1 ; i <= n ; i++){
        //~ for(int j = 1 ; j <= n ; j++){
            //~ grid[i][j] = color(i, j);
            //~ cout << grid[i][j] << " ";
        //~ }
        //~ cout << endl;
    //~ }
    while(ask(x + 1, y)) x = finddown(x, y);
    int h = findup(x, y);
    int m = x - h + 1;
    x = h;
    if(m % 3 == 0 && check(m / 3, x, y)) m /= 3;
    else if(m % 5 == 0 && check(m / 5, x, y)) m /= 5;
    y = findleft(x, y);
    //~ cout << "m: " << m << endl;
    assert(m % 2 && m > 1);
    for(int i = -5 ; i <= 5 ; i++){
        for(int j = -5 ; j <= 5 ; j++){
            if((i + j) % 2) continue;
            if(ask(x + i * m, y + j * m)){
                x += i * m;
                y += j * m;
                i = 6;
                break;
            }
        }
    }
    //~ assert(x == X && y == Y);
    answer(x + 2 * m + m / 2, y + 2 * m + m / 2);
    //~ cout << "asked: " << asked << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Execution timed out 3027 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -