Submission #556723

#	Time	Username	Problem	Language	Result	Execution time	Memory
556723		MohamedFaresNebili	Hotter Colder (IOI10_hottercolder)	C++14	100 / 100	643 ms	8680 KiB

hottercolder

#include <bits/stdc++.h>
#include "grader.h"

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        #define ub upper_bound
        /// #define int ll

        const int oo = 1e9 + 7;

        int Guess(int v);

        map<int, int> m; bool first = 1;
        void init() {
            for(int l = 1; l < 30; l++) {
                int i = ((1 << l + 1) + (l & 1 ? -1 : 1)) / 3;
                int j = ((1 << l) + (l & 1 ? -1 : 1) * 2) / 3 + 1;
                m[i] = j;
            }
        }

        int solve(int lo, int hi, int pr, int N, bool state) {
            if(state) return (lo + hi) / 2;
            if(pr == 1 || pr == N) {
                int calc;
                if(pr == 1) calc = lo * 2 - 2 + m.ub(hi - lo)->ss;
                if(pr == N) calc = hi * 2 - N + 1 - m.ub(hi - lo)->ss;
                calc = max(calc, 1);
                calc = min(calc, N);
                return calc;
            }
            int res = lo + hi - pr;
            res = max(res, 1); res = min(res, N);
            if(lo <= res && res <= hi && (hi - lo + 1) & 2) {
                if(res < pr && (res ^ lo) & 1 || res > pr && (res ^ hi) & 1) {
                    if(N - hi > lo - 1) res--;
                    else res++;
                }
            }
            if(res == pr) {
                if(N - hi > lo - 1) res--;
                else res++;
            }
            return res;
        }

        int HC(int N) {
            if(first) first = 0, init();
            int lo = 1, hi = N, pr = (lo + hi) / 2 + 1;
            pr = max(1, pr); pr = min(N, pr);
            Guess(pr); bool state = 1;
            while(lo < hi) {
                int to = solve(lo, hi, pr, N, state);
                if(state) state = 0;

              	if(to == pr && to - 1 >= lo) to--;
              	if(to == pr && to + 1 <= hi) to++;
              	if(to == pr) return to;

                int r = Guess(to), md = abs(to - pr);
                if(md & 1) md++;

                if(r == 0) return (to + pr) / 2;
                else if((r == 1 && to > pr) || (r == -1 && to < pr))
                    lo = max(lo, (to + pr) / 2 + 1);
                else hi = min(hi, (to + pr + 1) / 2 - 1);
                pr = to;
            }
            return lo;
        }

Compilation message (stderr)

hottercolder.cpp: In function 'void init()':
hottercolder.cpp:25:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |                 int i = ((1 << l + 1) + (l & 1 ? -1 : 1)) / 3;
      |                                ~~^~~
hottercolder.cpp: In function 'int solve(int, int, int, int, bool)':
hottercolder.cpp:44:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   44 |                 if(res < pr && (res ^ lo) & 1 || res > pr && (res ^ hi) & 1) {
      |                    ~~~~~~~~~^~~~~~~~~~~~~~~~~

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