oj.uz

Submission #393535

# Submission time Handle Problem Language Result Execution time Memory
393535 2021-04-23T19:06:13 Z jainbot27 Worm Worries (BOI18_worm) C++17
100 / 100
 1141 ms 500408 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define trav(x, y) for(auto&x:y)

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using pli=pair<ll, int>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;

template<class T> inline bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> inline bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl='\n';
const int mxN=2e5+10;
const int MOD=1e9+7;
const ll infLL=1e18;
const ld eps=1e-6;

int n, m, k, q;
vector<vector<vi>> vis;

int query(int N, int M=0, int K=0){
    if(N<0||M<0||K<0||N>=n||M>=m||K>=k) return 0;
    if(vis[N][M][K]!=-1) return vis[N][M][K];
    cout << "? " <<  N+1 << ' ' << M+1 << ' ' << K+1 << endl;
    cin >> vis[N][M][K]; return vis[N][M][K];
}

int answer(int N, int M=0, int K=0){
    cout << "! " << N+1 << ' ' << M+1 << ' ' << K+1 << endl;
    exit(0); 
}

void solve1(){
    int l=0, r=n-1, m1=-1, m2=-1, lst=0;
    while(l<r){
        swap(m1, m2); 
        if(lst!=1)
            m1=ceil(0.62*l+0.38*r);
        if(lst!=2)
            m2=floor(0.38*l+0.62*r);
        if(m1>m2) swap(m1, m2); 
        if(m1==m2) {
            if(m1>l) m1--; else m2++; 
        }
        assert(m1<m2);
        if(query(m1)>=query(m2))
            r=m2-1, lst=2; 
        else
            l=m1+1, lst=1;
    }
    answer(l);
}

void solve2(){
    int l1=0, r1=n-1, l2=0, r2=n-1, x=-1, y=-1;
    while(l1<r1||l2<r2){
        if(r1-l1>r2-l2){
            int m=(l1+r1)/2, a=m, b=l2; 
            FOR(i, l2, r2+1)
                if(query(m, i)>query(a, b))
                    a=m, b=i;
            if(query(a, b)<query(x, y)){
                if(x>a)
                    l1=m+1;
                else 
                    r1=m-1;
            } 
            else if(query(a+1, b)>query(a, b))
                l1=m+1, x=a, y=b;
            else if(query(a-1, b)>query(a, b))
                r1=m-1, x=a, y=b;
            else 
                answer(a, b);
        }
        else{
            int m=(l2+r2)/2, a=l1, b=m;
            FOR(i, l1, r1+1)
                if(query(i, m)>query(a, b))
                    a=i, b=m;
            if(query(a, b)<query(x, y)){
                if(y>b)
                    l2=m+1;
                else    
                    r2=m-1;
            }
            else if(query(a, b+1)>query(a, b))
                l2=m+1, x=a, y=b;
            else if(query(a, b-1)>query(a, b))
                r2=m-1, x=a, y=b;
            else 
                answer(a, b);
        }
    }
    answer(l1, l2);
}

void solve3(){
    int qq=0;
    int x=-1, y=-1, z=-1;
    while(qq++<50000){
        int a=rng()%n, b=rng()%m, c=rng()%k;
        if(query(a, b, c)>query(x, y, z)) 
            x=a, y=b, z=c;
    }
    int dx[]={0, 0, 0, 0, -1, 1};
    int dy[]={0, 0, -1, 1, 0, 0};
    int dz[]={-1, 1, 0, 0, 0, 0};
    while(true){
        int a, b, c; 
        bool good=1;
        F0R(d, 6){
            a=x+dx[d], b=y+dy[d], c=z+dz[d];
            if(query(a, b, c)>query(x, y, z)){
                good=0;
                break;
            }
        }
        if(good)
            answer(x, y, z);
        x=a, y=b, z=c;
    }
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k >> q;
    vis=vector<vector<vi>>(n, vector<vi>(m, vi(k, -1))); 
    if(m==1&&k==1) solve1();
    else if(k==1) solve2();
    else solve3();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 86344 KB Output is correct
2 Correct 123 ms 86292 KB Output is correct
3 Correct 127 ms 86316 KB Output is correct
4 Correct 118 ms 86336 KB Output is correct
5 Correct 119 ms 86284 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 86384 KB Output is correct
2 Correct 120 ms 86352 KB Output is correct
3 Correct 122 ms 86412 KB Output is correct
4 Correct 138 ms 86320 KB Output is correct
5 Correct 125 ms 86340 KB Output is correct
6 Correct 121 ms 86336 KB Output is correct
7 Correct 119 ms 86336 KB Output is correct
8 Correct 121 ms 86288 KB Output is correct
9 Correct 124 ms 86412 KB Output is correct
10 Correct 120 ms 86336 KB Output is correct
11 Correct 122 ms 86336 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 55096 KB Output is correct
2 Correct 106 ms 55104 KB Output is correct
3 Correct 81 ms 55148 KB Output is correct
4 Correct 112 ms 55180 KB Output is correct
5 Correct 106 ms 55104 KB Output is correct
6 Correct 99 ms 55136 KB Output is correct
7 Correct 127 ms 55092 KB Output is correct
8 Correct 99 ms 55104 KB Output is correct
9 Correct 102 ms 55104 KB Output is correct
10 Correct 110 ms 55064 KB Output is correct
11 Correct 99 ms 55100 KB Output is correct
12 Correct 107 ms 55068 KB Output is correct
13 Correct 96 ms 55104 KB Output is correct
14 Correct 91 ms 55080 KB Output is correct
15 Correct 104 ms 55176 KB Output is correct
16 Correct 106 ms 55104 KB Output is correct
17 Correct 83 ms 55100 KB Output is correct
18 Correct 108 ms 55140 KB Output is correct
19 Correct 112 ms 55104 KB Output is correct
20 Correct 102 ms 55084 KB Output is correct
21 Correct 129 ms 55064 KB Output is correct
22 Correct 82 ms 55180 KB Output is correct
23 Correct 111 ms 55056 KB Output is correct
24 Correct 135 ms 55148 KB Output is correct
25 Correct 111 ms 55160 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 4656 KB Output is correct
2 Correct 435 ms 4648 KB Output is correct
3 Correct 518 ms 4648 KB Output is correct
4 Correct 325 ms 4648 KB Output is correct
5 Correct 324 ms 4652 KB Output is correct
6 Correct 469 ms 4648 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 500408 KB Output is correct
2 Correct 704 ms 500336 KB Output is correct
3 Correct 742 ms 500336 KB Output is correct
4 Correct 589 ms 500332 KB Output is correct
5 Correct 643 ms 500340 KB Output is correct
6 Correct 765 ms 500288 KB Output is correct
7 Correct 757 ms 500336 KB Output is correct
8 Correct 752 ms 500344 KB Output is correct
9 Correct 1141 ms 500332 KB Output is correct
10 Correct 691 ms 500336 KB Output is correct
11 Correct 732 ms 500388 KB Output is correct