Submission #39801

#	Time	Username	Problem	Language	Result	Execution time	Memory
39801		0xrgb	Hotter Colder (IOI10_hottercolder)	C++11	100 / 100	1060 ms	8156 KiB

hottercolder

// Author: Gordon V. Cormack; solves Subtask 4
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdlib.h>
#include "grader.h"

int t[50];

#define max(a, b) ((a)>(b)?(a):(b))
#define min(a, b) ((a)<(b)?(a):(b))

int fix(int end, int x) {
   // returns value at x steps from end
   if (end == 1) return x;
   return end-x+1;
}

int midgame(int p, int a, int b) {
   // returns Jill's number, assuming
   // p = previous guess, [a .. b] = interval of remaining candidates
   if (a == b) return a;
   if (a > b) {
      int t = a;
      a = b;
      b = t;
   }
   // a < b
   int sz, mid=-999;
   for (sz=3; b-a+1 > sz; sz = 2*sz+1);
   if (p < b-sz+1) mid = b-sz/2;
   else if (p > a+sz-1) mid = a+sz/2;
   else if (p <= a) mid = p+sz/2;
   else if (p >= b) mid = p-sz/2;
   int q = mid + (mid-p);
   int g = Guess(q); // compares to mid
   if (g == 0) return mid;
   if (q > mid && g > 0 || q < mid && g < 0) return midgame(q, min(mid+1, b), b);
   return midgame(q, a, max(mid-1, a));
}

int endgame(int end, int n){
   // returns Jill's number, assuming
   // end = value on edge (1 or N); n = number of remaining candidate values
   int z, g;
   for (z=0; t[z]<n; z++);
   if (n == 2) {
      g = Guess(fix(end, 1));
      if (g > 0) return fix(end, 1);
      return fix(end, 2);
   }
   if (n == 3) {
      g = Guess(fix(end, 1));
      if (g > 0) return fix(end, 1);
      if (g == 0) return fix(end, 2);
      if (g < 0) return fix(end, 3);
   }
   if (n == 4 || n == 5) {
      g = Guess(fix(end, 3));
      if (g < 0) return fix(end, n);
      if (g == 0) return fix(end, 4);
      g = Guess(fix(end, 1));
      if (g > 0) return fix(end, 1);
      if (g == 0) return fix(end, 2);
      if (g < 0) return fix(end, 3);
   }
   if (n == 6) {
      g = Guess(fix(end, 1));
      if (g > 0) {
         g = Guess(fix(end, 3));
         if (g > 0) return fix(end, 3);
         if (g == 0) return fix(end, 2);
         if (g < 0) return fix(end, 1);
      }
      g = Guess(fix(end, 9));
      if (g > 0) return fix(end, 6);
      if (g == 0) return fix(end, 5);
      if (g < 0) return fix(end, 4);
   }
   if (n == 7) {
      g = Guess(fix(end, 1));
      if (g == 0) return fix(end, 4);
      if (g > 0) {
         int g = Guess(fix(end, 3));
         if (g > 0) return fix(end, 3);
         if (g == 0) return fix(end, 2);
         return fix(end, 1);
      }
      g = Guess(fix(end, 11));
      if (g > 0) return fix(end, 7);
      if (g == 0) return fix(end, 6);
      if (g < 0) return fix(end, 5);
   }
   g = Guess(fix(end, t[z-2]-2));
   if (g == 0) return fix(end, (t[z-2]-2+n)/2);
   if (g < 0) return midgame(fix(end, t[z-2]-2), fix(end, (t[z-2]-2+n)/2+1), fix(end, n));
   // g > 0
   g = Guess(fix(end, t[z-2]));
   if (g < 0) return endgame(end, t[z-2]);
   if (g == 0) return fix(end, t[z-2]-1);
   return midgame(fix(end, t[z-2]), fix(end, t[z-2]), fix(end, (t[z-2]-2+n-1)/2));
   return 0;
}

int HC(int N) {
   // returns Jill's number
   int i, mid;
   if (!t[0]) {
      t[0] = 1;
      t[1] = 3;
      t[2] = 7;
      for (i=3; i<30; i++) t[i] = t[i-2] + (1l<<i);
   }
   if (N == 1) return 1;
   if (N == 2) {
      Guess(1);
      i = Guess(2);
      if (i > 0) return 2;
      else return 1;
   }
   if (N == 3) {
      Guess(1);
      i = Guess(3);
      if (i > 0) return 3;
      if (i < 0) return 1;
      return 2;
   }
   mid = (N+2)/2;
   Guess(mid-2);
   i = Guess(mid);
   if (i == 0) return mid-1;
   if (i < 0) return endgame(1, mid);
   return endgame(N, N-mid+1);
}

Compilation message (stderr)

hottercolder.cpp: In function 'int midgame(int, int, int)':
hottercolder.cpp:38:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if (q > mid && g > 0 || q < mid && g < 0) return midgame(q, min(mid+1, b), b);
        ~~~~~~~~^~~~~~~~

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