Submission #554920

#	Time	Username	Problem	Language	Result	Execution time	Memory
554920		kevinxiehk	Hotter Colder (IOI10_hottercolder)	C++17	92 / 100	668 ms	8104 KiB

hottercolder

#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) / 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';
    
// }

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 17 / 25