oj.uz

Submission #328474

# Submission time Handle Problem Language Result Execution time Memory
328474 2020-11-16T17:27:02 Z MarcoMeijer Worm Worries (BOI18_worm) C++14
59 / 100
 643 ms 8840 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 876 KB Output is correct
2 Correct 31 ms 1132 KB Output is correct
3 Correct 24 ms 1004 KB Output is correct
4 Correct 27 ms 1004 KB Output is correct
5 Correct 25 ms 876 KB Output is correct

Subtask #2
0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 492 KB Output is correct
2 Correct 9 ms 492 KB Output is correct
3 Correct 10 ms 492 KB Output is correct
4 Correct 10 ms 492 KB Output is correct
5 Correct 14 ms 492 KB Output is correct
6 Correct 16 ms 492 KB Output is correct
7 Correct 14 ms 492 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 896 KB Output is correct
2 Correct 11 ms 492 KB Output is correct
3 Correct 10 ms 492 KB Output is correct
4 Runtime error 26 ms 1132 KB Execution killed with signal 13 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 2324 KB Output is correct
2 Correct 242 ms 2412 KB Output is correct
3 Correct 283 ms 2568 KB Output is correct
4 Correct 247 ms 2612 KB Output is correct
5 Correct 282 ms 2412 KB Output is correct
6 Correct 257 ms 2444 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 5412 KB Output is correct
2 Correct 397 ms 5740 KB Output is correct
3 Correct 360 ms 5404 KB Output is correct
4 Correct 491 ms 6892 KB Output is correct
5 Correct 420 ms 5740 KB Output is correct
6 Correct 376 ms 5740 KB Output is correct
7 Correct 467 ms 5740 KB Output is correct
8 Correct 482 ms 6636 KB Output is correct
9 Correct 643 ms 7276 KB Output is correct
10 Correct 412 ms 5760 KB Output is correct
11 Correct 627 ms 8840 KB Output is correct