oj.uz

Submission #93916

# Submission time Handle Problem Language Result Execution time Memory
93916 2019-01-13T08:30:43 Z Diuven Worm Worries (BOI18_worm) C++14
0 / 100
 1441 ms 9676 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, k, q;
map<tuple<int, int, int>, int> mem;

int cnt=0;

void solved(int x, int y, int z){
    cout<<"! "<<x<<' '<<y<<' '<<z<<endl;
    exit(0);
}

int ask(int x, int y, int z){
    if(x<1 || n<x || y<1 || m<y || z<1 || k<z) return 0;
    int &res=mem[{x,y,z}];
    if(res>0) return res;
    static int cnt=0; cnt++;

    if(cnt>q){
        pair<tuple<int, int, int>, int> mx; mx.first={1,1,1}, mx.second=0;
        for(auto &q:mem){
            if(q.second>mx.second) mx=q;
        }
        int x,y,z; tie(x,y,z)=mx.first;
        solved(x,y,z);
    }

    cout<<"? "<<x<<' '<<y<<' '<<z<<endl;
    cin>>res;


    if(res<0) exit(0);
    return res;
}

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

bool valid1(int x, int y, int z){
    int mx=ask(x,y,z);
    for(int k=0; k<6; k++) mx=max(mx, ask(x+dx[k], y+dy[k], z+dz[k]));
    return mx==ask(x,y,z);
}
bool valid2(int x, int y, int z){
    if(x<1 || n<x || y<1 || m<y || z<1 || k<z) return false;
    int mx=ask(x,y,z);
    for(int k=0; k<6; k++){
        int u=x+dx[k], v=y+dy[k], w=z+dz[k];
        if(mem.find({u,v,w})==mem.end()) return false;
        mx=max(mx, ask(u,v,w));
    }
    return mx==ask(x,y,z);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>k>>q;
    srand(time(NULL));
    while(true){
        int x=rand()%n+1, y=rand()%m+1, z=rand()%k+1;
        if(valid1(x,y,z)) solved(x,y,z);
        for(int k=0; k<6; k++){
            int u=x+dx[k], v=y+dy[k], w=z+dz[k];
            if(valid2(u,v,w)) solved(u,v,w);
        }
    }
    return 0;   
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 44 ms 844 KB not a local maximum
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Incorrect 2 ms 376 KB not a local maximum
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 37 ms 492 KB not a local maximum
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 33 ms 552 KB not a local maximum
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Incorrect 892 ms 6532 KB not a local maximum
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 1441 ms 9676 KB not a local maximum
3 Halted 0 ms 0 KB -