이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Guess(int n);
// int lastG = -1, X;
// int cnt = 0;
// int Guess(int n){
// cnt++;
// // cout << "GUESS: " << lastG << ", " << n << '\n';
// if(lastG == -1 || abs(X - lastG) == abs(X - n)){
// lastG = n;
// return 0;
// }
// if(abs(X - lastG) > abs(X - n)){
// lastG = n;
// return 1;
// }
// lastG = n;
// return -1;
// }
int HC(int n){
int l = 1, r = n;
int last = 1;
int R = rng() % 2;
if(R % 2 == 0){
last = 1;
Guess(1);
}
else{
last = n;
Guess(n);
}
while(l < r){
int mid = (l + r) >> 1;
// cout << l << ", " << r << ": " << last << '\n';
if(last == l){
int num = Guess(r);
last = r;
// cout << "NUM: " << num << '\n';
if(num == -1){
if((l + r) % 2)r = mid;
else r = mid - 1;
if(l == r)return l;
int R = rng() % 2;
if(R == 0){
Guess(l);
last = l;
}
else{
Guess(r);
last = r;
}
}
else if(num == 1){
l = mid + 1;
}
else{
return (l + r) >> 1;
}
}
else{
int num = Guess(l);
last = l;
// cout << "NUM: " << num << '\n';
if(num == 1){
if((l + r) % 2)r = mid;
else r = mid - 1;
}
else if(num == -1){
l = mid + 1;
if(l == r)return l;
int R = rng() % 2;
if(R == 0){
Guess(r);
last = r;
}
else{
Guess(l);
last = l;
}
}
else return (l + r) >> 1;
}
}
return l;
}
// int main(){
// int COUNTER = 0;
// for(int i = 1;i <= 500;++i){
// for(int j = 1;j <= i;++j){
// X = j;
// cnt = 0;
// lastG = -1;
// int found_num = HC(i);
// if(found_num != j){
// cout << "Wrong Answer: " << i << ", " << j << '\n';
// cout << "FOUND: " << found_num << '\n';
// break;
// }
// else if(cnt > 16){
// COUNTER++;
// cout << i << ", " << j << ": " << cnt << '\n';
// }
// }
// }
// cout << COUNTER;
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |