oj.uz

Submission #487409

# Submission time Handle Problem Language Result Execution time Memory
487409 2021-11-15T11:46:05 Z FatihSolak Worm Worries (BOI18_worm) C++17
32 / 100
 1 ms 292 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
map<vector<int>,int> mp;
int n,m,k,q;
int ask(int x,int y,int z){
    if(x < 1 || x > n)return 0;
    if(mp[{x,y,z}])return mp[{x,y,z}]; 
    cout << "? " << x << " " << y << " " << z << endl;
    int ret;
    cin >> ret;
    return mp[{x,y,z}] = ret;
}
void ans(int x,int y,int z){
    cout << "! " << x << " " << y << " " << z << endl;
    exit(0);
}
const double golden_ratio = (sqrt(5) - 1)/2;
void solve(){
    cin >> n >> m >> k >> q;
    if(m == 1 && k == 1){
        int l = 1,r = n;
        int x = golden_ratio * l + (1-golden_ratio)*r;
        int y = golden_ratio * r + (1-golden_ratio)*l;
        while(l + 5< r && x < y){
            if(ask(x,1,1) >= ask(y,1,1)){
                r = y - 1;
                y = x;
                x = golden_ratio * l + (1-golden_ratio)*r;
            }
            else{
                l = x + 1;
                x = y;
                y = golden_ratio * r + (1-golden_ratio)*l;
            }
        }
        for(int i=l;i<=r;i++){
            if(ask(i,1,1) >= ask(i-1,1,1) && ask(i,1,1) >= ask(i+1,1,1)){
                ans(i,1,1);
            }
        }
    }
}

int32_t main(){
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 232 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 0 ms 200 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -