oj.uz

Submission #1032927

# Submission time Handle Problem Language Result Execution time Memory
1032927 2024-07-24T10:56:39 Z anango Worm Worries (BOI18_worm) C++17
59 / 100
 720 ms 15720 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<30;
mt19937 rng;
vector<int> dx = {0,0,0,0,-1,1};
vector<int> dy = {0,0,-1,1,0,0};
vector<int> dz = {-1,1,0,0,0,0};

int n,m,k,q;

int qcount = 0;
int debug = 0;
vector<vector<vector<int>>> humidity;

vector<vector<int>> neighbours(vector<int> point) {
    vector<vector<int>> ans;
    for (int dir=0; dir<6; dir++) {
        int nx,ny,nz; nx=point[0]+dx[dir]; ny=point[1]+dy[dir]; nz=point[2]+dz[dir];
        if (!(1<=nx && nx<=n && 1<=ny && ny<=m && 1<=nz && nz<=k)) {
            continue;
        }
        ans.push_back({nx,ny,nz});
    }
    return ans;
}

map<vector<int>,int> cache;
int query(int x, int y, int z) {
    if (cache.count({x,y,z})) return cache[{x,y,z}];
    cout << "? " << x <<" " << y <<" " <<z << endl;
    qcount++;
    int an; 
    if (!debug) {
        cin >> an; 
    }
    else {
        cout << humidity[x-1][y-1][z-1] << endl;
        return cache[{x,y,z}] = humidity[x-1][y-1][z-1];
    }
    return cache[{x,y,z}] = an;
}

void answer(int x, int y, int z) {
    cout << "! " << x  << " " << y << " " << z << endl;
    if (debug) {
        cout << "in " << qcount <<" " << "queries" << endl;
        int gg=0;
        for (auto j:neighbours({x,y,z})) {
            if (humidity[j[0]-1][j[1]-1][j[2]-1]>humidity[x-1][y-1][z-1]) {
                gg=1;
            }
        }
        if (gg) {
            cout << "INCORRECT" << endl;
        }
        else {
            cout << "CORRECT" << endl;
        }
    }
}




signed main() {
    rng.discard((time(NULL))%100000);
    cin >> n >> m >> k >> q;
    if (debug) humidity = vector<vector<vector<int>>>(n,vector<vector<int>>(m,vector<int>(k,0)));
    if (debug) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                for (int k1=0; k1<k; k1++) {
                    humidity[i][j][k1]=rng();
                }
            }
        }
    }
    vector<vector<int>> points; //humidity,x,y,z
    int q1 = q/2;
    int q2 = q-q1;
    int pathlength = q2/6;
    for (int i=0; i<q1; i++) {
        int x,y,z; x=rng()%n; y=rng()%m; z=rng()%k; x++; y++; z++;
        points.push_back({query(x,y,z),x,y,z});
    }
    sort(points.begin(), points.end());
    reverse(points.begin(), points.end());
    int a,x,y,z;
    a = points[0][0]; x = points[0][1]; y = points[0][2]; z = points[0][3];
    while (1) {
        bool changed = 0;
        int ma=query(x,y,z);
        for (vector<int> j:neighbours({x,y,z})) {
            if (query(j[0],j[1],j[2])>ma) {
                x = j[0]; y=j[1]; z=j[2]; changed=1; ma=query(j[0],j[1],j[2]);
            }
        }
        if (!changed) break;
    }
    answer(x,y,z);
    
}

Compilation message

worm.cpp: In function 'int main()':
worm.cpp:82:9: warning: unused variable 'pathlength' [-Wunused-variable]
   82 |     int pathlength = q2/6;
      |         ^~~~~~~~~~
worm.cpp:89:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   89 |     int a,x,y,z;
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1384 KB Output is correct
2 Correct 34 ms 1496 KB Output is correct
3 Correct 28 ms 1100 KB Output is correct
4 Correct 29 ms 1104 KB Output is correct
5 Correct 32 ms 1300 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB too many queries. input: ? 971665 1 1
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 772 KB Output is correct
2 Correct 13 ms 600 KB Output is correct
3 Correct 11 ms 600 KB Output is correct
4 Correct 16 ms 600 KB Output is correct
5 Correct 15 ms 800 KB Output is correct
6 Correct 13 ms 856 KB Output is correct
7 Correct 12 ms 768 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 600 KB Output is correct
2 Correct 10 ms 600 KB Output is correct
3 Correct 9 ms 712 KB Output is correct
4 Correct 22 ms 880 KB Output is correct
5 Correct 12 ms 776 KB Output is correct
6 Runtime error 21 ms 888 KB Execution killed with signal 13
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 9908 KB Output is correct
2 Correct 359 ms 9364 KB Output is correct
3 Correct 359 ms 9296 KB Output is correct
4 Correct 365 ms 9592 KB Output is correct
5 Correct 427 ms 10048 KB Output is correct
6 Correct 378 ms 9104 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 13744 KB Output is correct
2 Correct 584 ms 14500 KB Output is correct
3 Correct 613 ms 14380 KB Output is correct
4 Correct 720 ms 15048 KB Output is correct
5 Correct 684 ms 14292 KB Output is correct
6 Correct 641 ms 14476 KB Output is correct
7 Correct 676 ms 14792 KB Output is correct
8 Correct 652 ms 14364 KB Output is correct
9 Correct 619 ms 14280 KB Output is correct
10 Correct 628 ms 14536 KB Output is correct
11 Correct 671 ms 15720 KB Output is correct