#include <bits/stdc++.h>
#include "grader.h"
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
using namespace std;
int Guess (int x);
int last = 1;
int ans;
int cnt = 0;
// int Guess (int x) {
// cnt++;
// // cout << x << '\n';
// if(abs(last - ans) == abs(x - ans)) return 0;
// else if(abs(last - ans) > abs(x - ans)) return 1;
// return -1;
// }
int HC(int n){
int l = 1, r = n;
// if(n >= 1000000) {
// Guess(1); last = 1;
// if(n >= 3) {
// int in = Guess(3); last = 3;
// if(in == 0) return 2;
// if(in == -1) return 1;
// }
// Guess(n); last = n;
// if(n >= 3) {
// int in = Guess(n - 2); last = n - 2;
// if(in == 0) return n - 1;
// if(in == -1) return n;
// }
// }
int init = (2 * n + 2) / 3;
last = max(1, init);
last = min(last, n);
Guess(last);
while(l < r) {
// if(last != l && last != r) {
// Guess(l); last = l;
// }
int mid, now;
mid = (l + r) / 2;
if(last > mid) mid = (l + r + 1) / 2;
now = mid * 2 - last;
if(now == last) {
if(mid == (l + r) / 2) now++;
else now--;
}
// cout << l << ' ' << r << ' ' << mid << ' ' << r - l + 1 << '\n';
// now = min(now, n); now = max(now, 1);
if(r - l + 1 >= n / 2 - 1) {
if(now > n) {
now = (r + l * 2 + 2) / 3;
}
if(now < 1) {
now = (r * 2 + l) / 3;
}
}
else {
now = min(now, n);
now = max(1, now);
}
// cout << "last = " << last << ", now = " << now << '\n';
int k = Guess(now);
// last = l ^ r ^ last;
if(k == 0) {
return (last + now) / 2;
}
else if((k == 1 && now > last) || (k == -1 && now < last)) {
l = max(l, (last + now) / 2 + 1);
}
else {
r = min(r, (last + now + 1) / 2 - 1);
}
last = now;
}
return l;
}
// mt19937 mt(time(nullptr));
// int main() {
// int mx = 0;
// int kk, kkk;
// // cin >> kk >> kkk;
// // ans = kk;
// // HC(kkk);
// // if(1.0 * cnt / ceil(log2(3 * kkk)) > 0) cout << 1.0 * cnt / ceil(log2(3 * kkk)) << '\n';
// // return 0;
// double t = 0;
// for(kk = 1; kk <= 10000000; kk += 1000){
// for(int w = kk; w <= kk + 1000; w++) {
// // int k = (1 << w) / 3;
// mx = 0;
// for(int i = w - 1000; i <= w + 1000; i++) {
// cnt = 0;
// int tc = i;
// tc = max(1, tc);
// if(i > w) tc = min(w, i - w);
// ans = tc;
// if(HC(w) != tc) cout << i << '\n';
// // mx = max(mx, cnt);
// if(1.0 * cnt / ceil(log2(3 * w)) > t) cout << 1.0 * cnt / ceil(log2(3 * w)) << ' ' << tc << ' ' << w << '\n';
// t = max(t, 1.0 * cnt / ceil(log2(3 * w)));
// }
// // cout << k << ' ' << mx << ' ' << 1.0 * mx / w << '\n';
// // t = max(t, 1.0 * mx / w);
// }}
// cout << 75 + 25 * (2 - t) << '\n';
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
618 ms |
8076 KB |
Output is partially correct - alpha = 0.666666666667 |
