Submission #1033083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033083		anango	Worm Worries (BOI18_worm)	C++17	100 / 100	758 ms	16524 KiB

worm

#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 curmax=-1; int xmax=-1; int ymax=-1;

int qcount = 0;
int debug = 0;
vector<vector<vector<int>>> humidity;
int getm1(int l, int r) {
    return (l*5+r*3)/8;
}

int getm2(int l, int r) {
    return (l*3+r*5)/8;
}

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 queryw(int x, int y, int z) {
    if (!(1<=x && x<=n && 1<=y && y<=m && 1<=z && z<=k)) {
        return -1;
    }
    if (cache.count({x,y,z})) return cache[{x,y,z}];
    cout << "? " << x <<" " << y <<" " <<z << endl;
    qcount++;
    if (qcount>=q-1) {
        while (1==1) {
            int o=0;
        }
    }
    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;
}

int query(int x, int y, int z) {
    int ans = queryw(x,y,z);
    if (ans>curmax) {
        curmax = ans; xmax = x; ymax = y;
    }
    return ans;
}

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 (m==1 && k==1) {
        int l = 1;
    int r = n;
    int known = getm1(l,r);
    int knownval = query(known,1,1);
    while (l<r-1) {
        int m1,m2,m1v,m2v;
        if ((r-known)<(known-l)) {
            //fill in m1
            m2 = known; m2v = knownval;
            m1 = getm1(l,r); 
            if (m1==m2 && m1>l) m1--;
            m1v = query(m1,1,1);
        }
        else {
            //fill in m2
            m1 = known; m1v = knownval;
            m2 = getm2(l,r); 
            if (m2==m1 && m2<r) m2++; 
            m2v = query(m2,1,1);
        }
        if (debug) cout << "binary search " << l <<" " << m1 <<" " << m2 <<" " << r <<" " << m1v <<" " << m2v << endl;
        if (m1v<m2v) {
            l=m1+1;
            r=r;
            known = m2;
            knownval = m2v;
        }
        else {
            l=l;
            r=m2-1;
            known = m1;
            knownval = m1v;
        }
    }
    if (query(l,1,1)<query(r,1,1)) answer(r,1,1);
    else answer(l,1,1);
    }
    else if (k>1) {
        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);
    }
    else { 
    if (debug) humidity = vector<vector<vector<int>>>(n,vector<vector<int>>(m,vector<int>(k,0)));
    if (debug) {
        int findx = 50;
        int findy = 7;
        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]=100000-(abs(i-findx)+abs(j-findy)+1);//rng()%10000;
                    cout << humidity[i][j][k1] <<" ";
                }
            }
            cout << endl;
        }
    }
    int lx,rx,ly,ry;
    int answered = 0;
    lx = 1; rx = n; ly = 1; ry = m;
    while (lx<rx || ly<ry) {
        if (debug) cout << "binsearch " << lx <<" " << rx <<" " << ly <<" " << ry << endl;
        if (rx-lx>ry-ly) {
            //split by x
            int mx = (lx+rx)/2;
            int ma = -1;
            int mi = -1;
            for (int y=ly; y<=ry; y++) {
                if (query(mx,y,1)>ma) {
                    ma = query(mx,y,1);
                    mi = y;
                }
            }
            assert(ma<=curmax);
            
            if ((query(mx+1,mi,1)>query(mx,mi,1) && ma==curmax) || (xmax>mx && ma<curmax)) {
                //go down
                lx=mx+1;
            
            }
            else if ((query(mx-1,mi,1)>query(mx,mi,1) && ma==curmax) || (xmax<mx && ma<curmax)) {
                rx = mx-1;
            }
            else {
                answer(mx,mi,1); answered = 1;
                break;
            }
        }
        else {
            //split by y
            int my = (ly+ry)/2;
            int ma = -1;
            int mi = -1;
            for (int x=lx; x<=rx; x++) {
                if (query(x,my,1)>ma) {
                    ma = query(x,my,1);
                    mi = x;
                }
            }
            assert(ma<=curmax);
            if ((query(mi,my+1,1)>query(mi,my,1)  && ma==curmax) || (ymax>my && ma<curmax)) {
                //go down
                ly=my+1;
            }
            else if ((query(mi,my-1,1)>query(mi,my,1) && ma==curmax) || (ymax<my && ma<curmax)) {
                ry=my-1;
            }
            else {
                answer(mi,my,1); answered = 1;
                break;
            }
        }
    }
    if (!answered) {
        answer(lx,ly,1);
    }
    }
}

Compilation message (stderr)

worm.cpp: In function 'long long int queryw(long long int, long long int, long long int)':
worm.cpp:47:17: warning: unused variable 'o' [-Wunused-variable]
   47 |             int o=0;
      |                 ^
worm.cpp: In function 'int main()':
worm.cpp:146:9: warning: unused variable 'pathlength' [-Wunused-variable]
  146 |     int pathlength = q2/6;
      |         ^~~~~~~~~~
worm.cpp:153:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  153 |     int a,x,y,z;
      |         ^

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23