oj.uz

Submission #173047

# Submission time Handle Problem Language Result Execution time Memory
173047 2020-01-03T08:22:40 Z gs13068 Hotter Colder (IOI10_hottercolder) C++17
100 / 100
 895 ms 8172 KB 
#include "grader.h"
#include <cmath>

int cal(int n) {
  return n < 5 ? 1 : (n + 1 >> 1) - cal(n >> 1);
}

int HC(int N){
  int L = 1, R = N, prv, nxt, t, W = log(3 * N) / log(2);
  while (L < R) {
    if (R == 2) {
      Guess(1);
      return Guess(2) < 0 ? 1 : 2;
    }
    int cut = W & 1 ? (2 << W - 2) / 3 + 1 : (2 << W - 2) / 3 + 2;
    nxt = R == N ? cut + cal(R - cut) : cut + cut - 1;
    prv = cut + cut - nxt;
    Guess(prv);
    t = Guess(nxt);
    if (t == -1) R = prv + nxt - 1 >> 1;
    if (t == 0) return prv + nxt >> 1;
    if (t == 1) {
      L = prv + nxt + 2 >> 1;
      prv = nxt;
      while (L < R) {
        nxt = (L + R >> 1 << 1) - prv;
        if (nxt == prv) nxt++;
        if (nxt < 1) nxt = 1;
        if (nxt > N) nxt = N;
        t = Guess(nxt);
        if (t == -1) {
          if (prv < nxt) R = nxt + prv - 1 >> 1;
          else L = nxt + prv + 2 >> 1;
        }
        if (t == 0) return nxt + prv >> 1;
        if (t == 1) {
          if (prv < nxt) L = nxt + prv + 2 >> 1;
          else R = nxt + prv - 1 >> 1;
        }
        prv = nxt;
      }
    }
    W -= 2;
  }
  return L;
}

Compilation message

hottercolder.cpp: In function 'int cal(int)':
hottercolder.cpp:5:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return n < 5 ? 1 : (n + 1 >> 1) - cal(n >> 1);
                       ~~^~~
hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:15:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     int cut = W & 1 ? (2 << W - 2) / 3 + 1 : (2 << W - 2) / 3 + 2;
                             ~~^~~
hottercolder.cpp:15:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     int cut = W & 1 ? (2 << W - 2) / 3 + 1 : (2 << W - 2) / 3 + 2;
                                                    ~~^~~
hottercolder.cpp:20:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
     if (t == -1) R = prv + nxt - 1 >> 1;
                      ~~~~~~~~~~^~~
hottercolder.cpp:21:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     if (t == 0) return prv + nxt >> 1;
                        ~~~~^~~~~
hottercolder.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       L = prv + nxt + 2 >> 1;
           ~~~~~~~~~~^~~
hottercolder.cpp:26:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         nxt = (L + R >> 1 << 1) - prv;
                ~~^~~
hottercolder.cpp:32:40: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
           if (prv < nxt) R = nxt + prv - 1 >> 1;
                              ~~~~~~~~~~^~~
hottercolder.cpp:33:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
           else L = nxt + prv + 2 >> 1;
                    ~~~~~~~~~~^~~
hottercolder.cpp:35:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         if (t == 0) return nxt + prv >> 1;
                            ~~~~^~~~~
hottercolder.cpp:37:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
           if (prv < nxt) L = nxt + prv + 2 >> 1;
                              ~~~~~~~~~~^~~
hottercolder.cpp:38:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
           else R = nxt + prv - 1 >> 1;
                    ~~~~~~~~~~^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1276 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1272 KB Output is correct

Subtask #4
25.0 / 25.0

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