Submission #284201

#	Time	Username	Problem	Language	Result	Execution time	Memory
284201		cjoa	Cave (IOI13_cave)	C++11	100 / 100	338 ms	632 KiB

cave

#include "cave.h"

#include <cstdio>

void exploreCave(int N) {
   int S[5004];
   int D[5004];
   int C[5004];

   for (int i = 0; i < N; ++i)
      S[i] = -1;

   for (int i = 0; i < N; ++i)
      D[i] = -1;

   for (int n = 0; n < N; ++n) {
      for (int i = 0; i < N; ++i)
         C[i] = S[i] >= 0 ? S[i] : 0;

   // fprintf(stderr, "n:%d ", n);
   // for (int i = 0; i < N; ++i)
   //    fprintf(stderr, "%d", C[i]);
   // fprintf(stderr, "\n");

      int first_closed_door = tryCombination(C);
      int is_cur_door_closed = first_closed_door == n;

   // fprintf(stderr, "first_closed_door:%d  is_cur_door_closed:%d\n",
   //         first_closed_door, is_cur_door_closed);

      int lo = 0, hi = N-1;
      while (lo < hi) {
         int mid = lo + (hi - lo) / 2;
         for (int i = lo; i <= mid; ++i)
            C[i] = S[i] >= 0 ? S[i] : 1;

         int door = tryCombination(C);

      // fprintf(stderr, "lo:%d  hi:%d  mid:%d  ", lo, hi, mid);
      // for (int i = 0; i < N; ++i)
      //    fprintf(stderr, "%d", C[i]);
      // fprintf(stderr, "  door:%d\n", door);

         if (is_cur_door_closed) {
            if (door == n) {
               // still closed
               lo = mid+1;
            }
            else {
               // door opened
               hi = mid;
            }
         }
         else {
            if (door != n) {
               // still opened
               lo = mid+1;
            }
            else {
               // door closed
               hi = mid;
            }
         }

         for (int i = lo; i <= mid; ++i)
            C[i] = S[i] >= 0 ? S[i] : 0;
      }
      
   // fprintf(stderr, "lo:%d\n", lo);

      // lo is the switch for door n
      D[lo] = n;
      S[lo] = is_cur_door_closed ? 1 : 0;

   }

   answer(S, D);
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24