oj.uz

Submission #680620

# Submission time Handle Problem Language Result Execution time Memory
680620 2023-01-11T10:59:34 Z Cross_Ratio Worm Worries (BOI18_worm) C++14
81 / 100
 907 ms 5712 KB 
#include <bits/stdc++.h>
using namespace std;
map<array<int, 3>, int> Ma;
int N, M, K;
int query_cnt = 0;
int query(int a, int b, int c) {
    if(!(1<=a&&a<=N&&1<=b&&b<=M&&1<=c&&c<=K)) return -1;
    if(Ma.count({a, b, c})) return Ma[{a, b, c}];
    query_cnt++;
    cout << "? " << a << ' ' << b << ' ' << c << endl;
    int d;
    cin >> d;
    Ma[{a, b, c}] = d;
    return d;
}
void answer(int a, int b, int c) {
    cout << "! " << a << ' ' << b << ' ' << c << endl;
    return;
}
int fibo[44];
void subtask_12() {

    int s = 1, e = fibo[30]+1;
    int x = fibo[28]+1, y = fibo[29]+1;
    while(s<=e) {
        if(s==e) {
            answer(s, 1, 1);
            return;
        }
        if(s+1==e) {
            if(query(s, 1, 1) >= query(e, 1, 1)) {
                answer(s, 1, 1);
                return;
            }
            else {
                answer(e, 1, 1);
                return;
            }
        }
        if(s+100>=e) {
            int mid = (s + e) / 2;
            if(query(mid, 1, 1) < query(mid+1, 1, 1)) {
                s = mid + 1;
            }
            else {
                e = mid;
            }
            continue;
        }
        if(query(x, 1, 1) >= query(y, 1, 1)) {
            e = y;
            y = x;
            x = (s+e) - y;
        }
        else {
            s = x;
            x = y;
            y = (s+e) - x;
        }
    }
}
void subtask_34() {
    int sx = 1, ex = N, sy = 1, ey = M;
    int rev = 0;
    int i, j;
    while(true) {
        if(sx==ex&&sy==ey) {
            assert(query(sx, sy, 1) >= query(sx-1, sy, 1));
            assert(query(sx, sy, 1) >= query(sx+1, sy, 1));
            assert(query(sx, sy, 1) >= query(sx, sy+1, 1));
            assert(query(sx, sy, 1) >= query(sx, sy-1, 1));
            answer(sx, sy, 1);
            return;
        }
        /*if(sx==ex&&sy+1==ey) {
            if(query(sx, sy, 1) >= query(sx, ey, 1)) {
                answer(sx, sy, 1);
                return;
            }
            else {
                answer(sx, ey, 1);
                return;
            }
        }
        if(sx+1==ex&&sy==ey) {
            if(query(sx, sy, 1) >= query(ex, sy, 1)) {
                answer(sx, sy, 1);
                return;
            }
            else {
                answer(ex, sy, 1);
                return;
            }
        }*/
        if(rev) {
            if(sx<ex) {
                int mid = (sx+ex)/2;
                int ma = -1, ix = -1;
                for(i=sy;i<=ey;i++) {
                    for(int j = mid; j <= mid+1; j++) {
                        if(ma < query(j, i, 1)) {
                            ma = query(j, i, 1);
                            ix = j;
                        }
                    }
                }
                assert(ix!=-1);
                if(ix==mid) ex = mid;
                else sx = mid + 1;
            }
        }
        else {
            if(sy<ey) {
                int mid = (sy+ey)/2;
                int ma = -1, iy = -1;
                for(i=sx;i<=ex;i++) {
                    for(int j = mid; j <= mid+1; j++) {
                        if(ma < query(i, j, 1)) {
                            ma = query(i, j, 1);
                            iy = j;
                        }
                    }
                }
                assert(iy!=-1);
                if(iy==mid) ey = mid;
                else sy = mid + 1;
            }
        }
        rev = 1 - rev;
    }
}
void subtask_56() {

}
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
void subtask_naive() {
    int ma = -1, ix = -1, iy = -1, iz = -1;
    int loop = (K==1?100:10000);
    while(loop--) {
        int x = rand() % N + 1, y = rand() % M + 1, z = rand() % K + 1;
        if(ma < query(x, y, z)) {
            ma = query(x, y, z);
            ix = x, iy = y, iz = z;
        }
    }
    int x = ix, y = iy, z = iz;
    int lim = (K==1?4:6);
    while(true) {
        int val = query(x, y, z);
        bool isPos = true;
        for(int i=0;i<lim;i++) {
            if(val < query(x+dx[i], y+dy[i], z+dz[i])) {
                x += dx[i], y += dy[i], z += dz[i];
                isPos = false;
                break;
            }
        }
        if(isPos) {
            answer(x, y, z);
            return;
        }
    }
}
signed main() {
    fibo[0] = fibo[1] = 1;
    int fibosum = 0;
    for(int i = 2 ; i <= 43; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
        //cout << i << " : " << fibo[i] << '\n';
    }
    for(int i = 0; i <= 15; i++) fibosum += fibo[i];
    //cout << fibosum*4 << '\n';
    int Q;
    cin >> N >> M >> K >> Q;
    if(M==1 && K == 1) {
        subtask_12();
    }
    else if(K==1 && N==M) {
        subtask_naive();
    }
    else if(K==N && K==M) {
        subtask_naive();
    }
    //cout << query_cnt;
}

Compilation message

worm.cpp: In function 'void subtask_34()':
worm.cpp:65:12: warning: unused variable 'j' [-Wunused-variable]
   65 |     int i, j;
      |            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 304 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 2 ms 284 KB Output is correct
4 Correct 8 ms 352 KB Output is correct
5 Correct 4 ms 296 KB Output is correct
6 Correct 11 ms 336 KB Output is correct
7 Correct 10 ms 324 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Runtime error 31 ms 500 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 844 KB Output is correct
2 Correct 132 ms 808 KB Output is correct
3 Correct 88 ms 876 KB Output is correct
4 Correct 81 ms 788 KB Output is correct
5 Correct 69 ms 964 KB Output is correct
6 Correct 98 ms 1004 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 792 KB Output is correct
2 Correct 115 ms 844 KB Output is correct
3 Correct 92 ms 992 KB Output is correct
4 Correct 204 ms 1492 KB Output is correct
5 Correct 434 ms 4112 KB Output is correct
6 Correct 112 ms 1040 KB Output is correct
7 Correct 292 ms 3100 KB Output is correct
8 Correct 428 ms 2580 KB Output is correct
9 Correct 566 ms 3308 KB Output is correct
10 Correct 907 ms 5712 KB Output is correct
11 Correct 890 ms 5460 KB Output is correct