oj.uz

Submission #304858

# Submission time Handle Problem Language Result Execution time Memory
304858 2020-09-22T03:06:53 Z tatyam Hotter Colder (IOI10_hottercolder) C++17
100 / 100
 816 ms 24568 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1280 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1280 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1280 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 816 ms 24568 KB Output is partially correct - alpha = 1.000000000000