oj.uz

Submission #784165

# Submission time Handle Problem Language Result Execution time Memory
784165 2023-07-15T19:42:42 Z canadavid1 Aliens (IOI07_aliens) C++14
100 / 100
 2 ms 208 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
#define int int64_t
//#define GRADING
//#define RANDOM
#ifdef RANDOM
#ifndef GRADING
#define GRADING
#endif
#endif
#define binary_search(op) while(r-l>1) {int m=(r+l)/2; if (op) r = m; else l = m;}
int N,X0,Y0;

random_device true_random;
mt19937 rng(true_random());


#ifdef GRADING
vector<vector<bool>> grid;
int counter=0,Xc,Yc,_M;
void grading_init()
{
    int M;
    #ifndef RANDOM
    cin >> N >> M >> X0 >> Y0 >> Xc >> Yc;
    #else
    cin >> N;
    uniform_int_distribution dist(1,N/15-1);
    M = dist(rng)*2+1;
    uniform_int_distribution c(1+2*M+M/2,N-2*M-M/2);
    Xc = c(rng);
    Yc = c(rng);
    vector<pair<int,int>> choices;
    #endif
    grid.assign(N+1,vector<bool>(N+1,false));
    assert(M%2==1);
    assert(M>=3);
    assert(Xc-2*M-M/2 >= 1);
    assert(Yc-2*M-M/2 >= 1);
    assert(Xc+2*M+M/2 <= N);
    assert(Yc+2*M+M/2 <= N);
    for(int i = -2; i <= 2; i++)
        for(int j = -2; j <= 2; j++)
            if((i+j)%2==0) 
                for(int y=-M/2; y<=M/2; y++)
                    for(int x=-M/2; x<=M/2;x++)
                    {
                        grid[i*M+y+Yc][j*M+x+Xc] = true;
                        #ifdef RANDOM
                        choices.push_back({i*M+y+Yc,j*M+x+Xc});
                        #endif
                    }
    #ifdef RANDOM
    uniform_int_distribution<int> c2(0,choices.size()-1);
    tie(Y0,X0) = choices[c2(rng)];
    #endif
    assert(grid[Y0][X0]);
    _M= M;
        
}
void grading_end(int X,int Y)
{
    if(X!=Xc || Y!=Yc)
    {
        // print original data
        cout << N << " " <<_M << " " << X0 << " " << Y0 << " "<< Xc << " " << Yc << " error (got " << X << " " << Y << ")\n";
        exit(1);
    }
    assert(X==Xc);
    assert(Y==Yc);
    cout << counter << " ok\n";
}
#endif

bool query(int x, int y)
{
    if(x <= 0 || x > N || y <= 0 || y > N) return 0;
    #ifdef GRADING
    counter++;
    return grid[y][x];
    #else
    cout << "examine " << x << " " << y << "\n" << flush;
    string out;
    cin >> out;
    return out=="true";
    #endif
}
#ifdef GRADING
void print()
{
    cout << "  ";
    for(int i = 1; i <= N; i++) cout << i/10;
    cout << "\n  ";
    for(int i = 1; i <= N; i++) cout << i%10;
    cout << "\n";
    for(int i = 1; i <= N; i++)
    {
        cout << i / 10 << i%10;
        for(int j = 1; j<=N; j++) cout << (grid[i][j] ? '*' : '.');
        cout << "\n";
    }
}
#endif

signed main()
{
    #ifdef GRADING
        grading_init();
        

        int X0=::X0,Y0=::Y0; // reduce global clutter
    #else
        int X0,Y0;
        cin >> N >> X0 >> Y0;
    #endif
    int i = 1;
    while(query(X0-i,Y0)) i*=2;
    int l=X0-i,r=X0;
    binary_search(query(m,Y0));
    int left_border = r;

    i = 1;
    while(query(X0+i,Y0)) i*=2;
    l=X0,r=X0+i;
    binary_search(!query(m,Y0));
    int right_border = l;

    i = 1;
    while(query(X0,Y0-i)) i*=2;
    l=Y0-i,r=Y0;
    binary_search(query(X0,m));
    int top_border = r;
    
    int M = right_border - left_border + 1; // inclusive bounds
    Y0 = top_border + M/2;
    X0 = left_border + M/2;
    while(query(X0-2*M,Y0)) X0 -= 2*M;
    while(query(X0,Y0-2*M)) Y0 -= 2*M;
    if(query(X0-M,Y0-M)) {X0-=M;Y0-=M;}
    X0+=2*M;
    Y0+=2*M;
    #ifdef GRADING
    grading_end(X0,Y0);
    #else
    cout << "solution " << X0 << " " << Y0 << "\n";
    #endif
}

Subtask #1
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 #2
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 #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 0 ms 208 KB Output is correct
2 Correct 0 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 208 KB Output is correct

Subtask #6
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

Subtask #7
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
3 Correct 1 ms 208 KB Output is correct

Subtask #8
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
3 Correct 2 ms 208 KB Output is correct

Subtask #9
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 #10
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
3 Correct 2 ms 208 KB Output is correct