Submission #304858

#	Time	Username	Problem	Language	Result	Execution time	Memory
304858		tatyam	Hotter Colder (IOI10_hottercolder)	C++17	100 / 100	816 ms	24568 KiB

hottercolder

#include <bits/stdc++.h>
using namespace std;

int Guess(int G);

struct T{
    map<int, int> a;
    T(){
        for(int n = 1; n < 30; n++){
            const int x = ((1 << n + 1) + (n & 1 ? -1 : 1)) / 3;
            const int y = ((1 << n) + (n & 1 ? -1 : 1) * 2) / 3 + 1;
            a[x] = y;
        }
    }
    int operator[](int x) const {
        return a.upper_bound(x)->second;
    }
} edge;

int HC(int N){
    if(N == 1) return 1;
    int l = 1, r = N, p = (l + r) / 2 + 1;
    Guess(p);
    bool first = 1;
    while(l < r){
        const int p2 = [&]{
            if(first){
                first = 0;
                return (l + r) / 2;
            }
            if(p == 1){
                return clamp(l * 2 - 2 + edge[r - l], 1, N);
            }
            if(p == N){
                return clamp(r * 2 - N + 1 - edge[r - l], 1, N);
            }
            int ans = clamp(l + r - p, 1, N);
            if(l <= ans && ans <= r && (r - l + 1) & 2) if(ans < p && (ans ^ l) & 1 || ans > p && (ans ^ r) & 1){
                if(N - r > l - 1) ans--;
                else ans++;
            }
            if(ans == p){
                if(N - r > l - 1) ans--;
                else ans++;
            }
            return ans;
        }();
        int ans = Guess(p2);
        if(ans == 0) return (p + p2) / 2;
        if(ans == 1){
            if(p2 < p) r = (p + p2 - 1) / 2;
            else l = (p + p2 + 2) / 2;
        }
        else{
            if(p2 < p) l = (p + p2 + 2) / 2;
            else r = (p + p2 - 1) / 2;
        }
        p = p2;
    }
    return l;
}

Compilation message (stderr)

hottercolder.cpp: In constructor 'T::T()':
hottercolder.cpp:10:36: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   10 |             const int x = ((1 << n + 1) + (n & 1 ? -1 : 1)) / 3;
      |                                  ~~^~~
hottercolder.cpp: In lambda function:
hottercolder.cpp:38:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |             if(l <= ans && ans <= r && (r - l + 1) & 2) if(ans < p && (ans ^ l) & 1 || ans > p && (ans ^ r) & 1){
      |                                                            ~~~~~~~~^~~~~~~~~~~~~~~~

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