Submission #328474

#	Time	Username	Problem	Language	Result	Execution time	Memory
328474		MarcoMeijer	Worm Worries (BOI18_worm)	C++14	59 / 100	643 ms	8840 KiB

worm

#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
//===================//
//  Added libraries  //
//===================//
 
//===================//
//end added libraries//
//===================//
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;

int n, m, k, q;
int dx[]={-1,1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
map<int,map<int,map<int,int>>> mp;

bool inside(int x, int y, int z) {return x>=1 && x<=n && y>=1 && y<=m && z>=1&&z<=k;}
int query(int x, int y, int z) {
    if(mp[x][y][z] != 0)
        return mp[x][y][z];
    OUTLS("?",x,y,z);
    cout.flush();
    int res; IN(res);
    return mp[x][y][z] = res;
}
void search(int x, int y, int z) {
    int val = query(x,y,z);
    int bst=0, bx, by, bz;
    RE(d,8) {
        int nx = x+dx[d];
        int ny = y+dy[d];
        int nz = z+dz[d];
        if(!inside(nx,ny,nz)) continue;
        int nVal = query(nx,ny,nz);
        if(nVal >= bst)
            bx=nx, by=ny, bz=nz, bst=nVal;
    }
    if(bst <= val) {
        OUTLS("!",x,y,z);
        return;
    } else {
        search(bx,by,bz);
    }
}

void program() {
    IN(n,m,k,q);
    
    int bst=0, bx, by, bz;
    RE(i,q/4) {
        int cx=rng()%n+1;
        int cy=rng()%m+1;
        int cz=rng()%k+1;
        int cr=query(cx,cy,cz);
        if(cr >= bst)
            bx=cx, by=cy, bz=cz, bst=cr;
    }

    search(bx,by,bz);
}

Compilation message (stderr)

worm.cpp: In function 'void search(int, int, int)':
worm.cpp:88:24: warning: iteration 6 invokes undefined behavior [-Waggressive-loop-optimizations]
   88 |         int nx = x+dx[d];
      |                    ~~~~^
worm.cpp:15:39: note: within this loop
   15 | #define REP(a,b,c) for(int a=int(b); a<int(c); a++)
      |                                       ^
worm.cpp:16:17: note: in expansion of macro 'REP'
   16 | #define RE(a,c) REP(a,0,c)
      |                 ^~~
worm.cpp:87:5: note: in expansion of macro 'RE'
   87 |     RE(d,8) {
      |     ^~
worm.cpp:100:15: warning: 'bz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |         search(bx,by,bz);
      |         ~~~~~~^~~~~~~~~~
worm.cpp:100:15: warning: 'by' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:100:15: warning: 'bx' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp: In function 'void program()':
worm.cpp:117:11: warning: 'bz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |     search(bx,by,bz);
      |     ~~~~~~^~~~~~~~~~
worm.cpp:117:11: warning: 'by' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:117:11: warning: 'bx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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